Lexicographic Permutations

This post describes how to generate the lexicographic permutations of a sequence. The lexicographic order is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters. This generalization consists primarily in defining a total order over the sequences of elements of a finite totally ordered set. You may understand that this is a way to establish ordering between sequences based on how their elements compare.

Algorithm description

There exist several ways to generate all permutations of a given sequence. The simple algorithm which I will discuss here is based on finding the next permutation in lexicographic ordering, if it exists, or reversing the last permutation to get back to the minimal permutation. This method goes back to Narayana Pandita in 14th century India.

The algorithm is quite straightforward and may be memorized:

Find the biggest i such that a[i] < a[i + 1];
Find the biggest j greater than i such that a[j] > a[i];
Swap a[i] and a[j];
Reverse the elements from a[i + 1] to the last element.

If the first step fails (because such index does not exist) the current permutation is the last one.

Given any permutation of a list, this generates the next one. It should be noted, however, that when given the greatest lexicographic permutation, this algorithm returns this same permutation, so it should be checked to ensure that if the permutation at hand is the last one, we reverse the sequence to get back to the first permutation.

This algorithm is simple to implement correctly, computationally efficient, and it only generates each distinct permutation once, which is convenient when there are many repeated elements.

Python implementation

Below is an in-place Python 3 implementation of the described algorithm. If you do not want mutability, wrap the algorithm calls with a function that copies the list. However, take into consideration that for very large lists this may use a significant amount of memory if you are interested in several permutations.

def swap(elements, i, j):
    elements[i], elements[j] = elements[j], elements[i]


def reverse(elements, i, j):
    for offset in range((j - i + 1) // 2):
        swap(elements, i + offset, j - offset)


def next_permutation(elements):
    last_index = len(elements) - 1
    if last_index < 1:
        return

    i = last_index - 1
    while i >= 0 and not elements[i] < elements[i + 1]:
        i -= 1

    # If there is no greater permutation, return to the first one.
    if i < 0:
        reverse(elements, 0, last_index)
    else:
        j = last_index
        while j > i + 1 and not elements[j] > elements[i]:
            j -= 1

        swap(elements, i, j)
        reverse(elements, i + 1, last_index)

Documentation was omitted for the sake of brevity. One could also consider this an example of code as documentation.

Algorithm output

Generating eight permutations of the string ‘abc’ in ascending lexicographic order produces the following sequence:

abc, acb, bac, bca, cab, cba, abc, acb, ...

Notice that after the sixth permutation we get back to the first one, as there are only six distinct permutations of the string ‘abc’.

Algorithm complexity

This algorithm uses constant additional space (as it is in-place) and has linear time complexity in the worst case but is amortized to constant time.

Concealed Squares

This is my solution to Project Euler problem number

  1. Although a brute force solution can be easily derived, this approach makes use of mathematical analysis to find the answer in less time. The problem statement follows.

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit.

It can be shown that the answer lies in the range R.

R = [floor(sqrt(1020304...00)), ceiling(sqrt(192939..90))] = [1010101010, 1389026624]

R has 378,925,614 integers, which is a lot to test quickly. Fortunately, one can reduce it by noticing that the square of the integer is divisible by 10, which implies that the integer too is divisible by 10. This leaves us with the possible solution set P.

P = {1010101010, 1010101020, ..., 1389026620}

The largest possible number is 19293949596979899990, which requires 65 bits to be represented as an unsigned integer. However, because we know that the answer is a multiple of 10, we also know that the square of the answer is a multiple of

  1. And, therefore, that it ends with 00. This allows for another optimization: divide all numbers in P by 10 and find the one whose square is of the form 1_2_3_4_5_6_7_8_9. These numbers fit into 64-bit words, so arithmetic with them will not be specially expensive.

P has 37,892,561 elements, but we do not need to check all of them. If x2 ends in 9, x ends in 3 or 7, which reduces by 80% the number of values we have to test.

Using Clang with the O3 flag, my C++ implementation of the algorithm finishes after 120 ms, which is a good enough solution for this problem.

Solving Tic-tac-toe using Racket

I decided to implement a perfect AI (using Minimax) for Tic-tac-toe. I had not decided though whether I’d use JavaScript or Racket, two languages I’ve been using quite a bit recently and about which I am quite interested. As the post title gives off, I’ve decided to write a functional programming solution using Racket. It is open-source and available on GitHub. See the repository. There is also a fairly decent GUI-based game that allows you to play against the AI.

GUI-based Tic-tac-toe game

When writing this I decided to use vectors instead of lists, expecting it would give me better performance. However, it is quite slow. Even though the current implementation is good enough for real-time gameplay, it could be much more efficient for such a simple decision tree as the one used in Tic-tac-toe. Maybe using lists would have been a better choice as some parts of the application now have to convert vectors to lists. Additionally, slicing and merging vectors seem to generate a lot of work for the garbage collector. Finally, as the biggest vector holds only nine elements, the constant-time random access vectors provide is likely not making too much of a difference.

Being an automation enthusiast myself. This project also got its amount of continuous integration and delivery. Every push and pull request is built and tested by Travis CI. Here you can find the build history of the project. Travis also prepares and deploys a Linux-only standalone distribution to GitHub releases on tags. See the releases page. In the future I may make Windows and Mac OS X standalone distributions available. You should be able to play the standalone game on Linux even without having Racket installed.

There is also alpha-beta pruning left to be implemented, which should also significantly improve performance. Even though this is still a work in progress, the game works and the AI is indeed perfect. It also runs in any operating system as long as it has a Racket 6 distribution installed.

Lyrics is now GuessSong

After working on Lyrics for some months on the days I found some time for it, I decided to take it to the next level. I went to Namecheap (my experience with GoDaddy hasn’t been good) and bought myself a domain good enough for it. As one would assume, lyrics.com was already taken. However, I managed to get guesssong.com, which makes a pretty decent name for the game and is not used for anything else already.

DNS changes have already been made and email has been properly set up, so now you can find GuessSong on www.guesssong.com and email me about it at contact@guesssong.com.

Site Statistics

This is my first variable post. By variable post I mean a post that might change at every recompilation of the website.

I had this idea when thinking about getting a word count of the project. Instead of just computing the word count for myself, I decided to make it into an always up-to-date blog post.

Basic statistics

Word count 25131
Post count 42
Page count 58
Mean word count per post 256
Mean word count per page 247

Extrapolated statistics

The average English reader would take 84 minutes to read the whole website, whose content amount is equivalent to that of 126 songs or 5 short stories.