Indian Computing Olympiad

Training Material


Generating permutations

In many problems, we have to systematically search through a set of possible "states" or "configurations" in order to find the answer. The overall solution is a loop of the form

       while (there is one more state to examine){
          generate the next state;
          if (the new state has the desired property){
             do something useful;
          }
       }
      

In many such search problems, one needs to be able to systematically generate all possible permutations of a given sequence of symbols.

For instance, given the sequence s = "a b c d", the set of permutations of s is {"a b c d", "a b d c", "a d b c", "a d c b", ..., "d c b a"}. Clearly, a sequence of length n generates n! permutations (we assume that all symbols in the sequence are distinct).

Our problem is to systematically generate all permutations of the sequence in lexicographic order; that is, the order in which the permutations would be listed in a dictionary. To achieve this, we would like a simple rule to determine the next permutation from the current one. We can then begin with the smallest permutation (arrange the symbols in ascending order) and keep applying this rule till we reach the largest permutation (all symbols in descending order).

Consider the following permutation over the letters {a,b,...,l}

f g j l b e c k i h d a

How do we get the next permutation?

Begin from the right and keep moving left as long as the letters are increasing in value (where a<b<c<…<l). In this case, start with a and scan past d, h, i, k. Stop at c because c<k.

Find the smallest value bigger than c in the sequence "k i h d a" after c and swap it with c. In this case, this value is d, so rewrite the last 6 letters of the sequence as "d k i h c a". Having done this, reverse the letters beyond d to get "d a c h i k".

The new permutation that we want is thus

f g j l b e d a c h i k

Why does this work? Given values a1<a2<...<ak, the smallest permutation is a1 a2 ... ak and the largest permutation is ak ... a2 a1.

For the element we have identified in the current permutation, there is no way to increment the permutation keeping this element fixed because we have already identified the largest permutation to its right. Thus, we have to increment the current element minimally, which is achieved by picking the next largest element to its right.

How do we implement this?

  1. Initially, sort the elements to obtain the minimum permutation.
  2. Scan from the right to find which element to increment.
  3. We now scan back to the right to find the next bigger element to replace this one. Observe that the sequence to the right is sorted in descending order, so this can be done using binary search.
  4. Finally, we have to reorder the elements to the right in ascending order. If at Step 3 we swap the new value with the value we want to increment, the sequence to the right remains in descending order. We just have to invert this sequence to put it in ascending order --- no sorting is required.

Some problems involving permutations