Efficient Permutations In Lexicographic Order
Aug 31, 2020
In this post, I want to show you a method to generate sorted permutations of a set. We will focus on generating these permutations in lexicographic or numeric order. There are several ways to do this, but some are better than others in terms of efficiency.
We'll also look at a method to obtain a permutation at an arbitrary position in our lexicographically ordered sequence. With this method, we can generate the permutation we're looking for more directly. We won't need to generate any of the previous permutations in the sequence that come before our target one.
Let's start by refreshing our memory on what a permutation is.
What Is a Permutation?
From combinatorics, a permutation–also called “order”–is the number of rearrangements of elements in a set. The number of permutations on a set of $n$ elements is given by $n!$ (n factorial). For example, in the set $\{1, 2, 3\}$ there are $3! = 3\times2\times1 = 6$ permutations:
$\{1 ,2, 3\},$ $\{1, 3, 2\},$ $\{2, 1, 3\},$ $\{2, 3, 1\},$ $\{3, 1, 2\},$ $\{3, 2, 1\}$.
The number of ways to rearrange a subset of $k$ elements out of a set of $n$ elements is given by:
$$\frac{n!}{(n-k)!}$$
This formula is easily derived from our previous definitions. Let’s follow a concrete example to illustrate this. Suppose we want to find the number of ways to arrange 4 books from a collection of 10. According to our formula above, we have:
$$\frac{10!}{(10-4)!}$$
We can think about this in the following way. In the numerator, we have the number of ways to arrange 10 books–that is $10!$ But, we only care about the first 4 ways. So, we divide out the remaining 6 ways–or $( 10-4)! = 6!$:
$\frac{10!}{(10-4)!} = \frac{10!}{6!} = \frac{10\times9\times8\times7\times(6\times5\times4\times3\times2\times1)}{(6\times5\times4\times3\times2\times1)}$
Finally, keep in mind that in a permutation, we count all possible orderings in a set.
Generating Permutations
We can generate permutations using different methods. And, depending on the method we choose, the order of the resulting permutations will change. Also, some methods will be more efficient than others. Robert Sedgewick concluded in his survey paper Permutation Generation Methods that the fastest algorithm to generate permutations is Heap’s algorithm. However, the resulting rearrangements from this method are not in lexicographic order.
Permutations in Lexicographic Order
In our case, we want to list them in lexicographic–or numerical–order. As an example, let’s generate the permutations of the set $\{0 1 2\}$. We take the smallest number, 0, and put it at the front then we append the remaining 1 and 2. This gives us the first permutation $\{0 1 2\}$. Next, keeping 0 in front, we rearrange 1 and 2: $\{0 2 1\}$. We repeat the process, but now with 1 at the front. So, we obtain permutations $\{1 0 2\}$ and $\{1 2 0\}$. Finally, we repeat with 2 at the front: $\{2 0 1\}$ and $\{2 1 0\}$. The resulting permutations list is the following.
- $\{0 1 2\}$
- $\{0 2 1\}$
- $\{1 0 2\}$
- $\{1 2 0\}$
- $\{2 0 1\}$
- $\{2 1 0\}$
Notice that the list is arranged in numerical order. In other words, each subsequent arrangement of the numbers is greater than the previous one.
In this example, we only had 6 permutations of the set $\{1 2 3\}$. So, it was easy to list them all. However, as the size of the set starts to grow, the number of permutations increases even faster. Remember that it follows a factorial rate of growth–the number of permutations of a set of size $n$ = $n!$ So, if we wanted to generate the permutations of the set $\{0 1 2 3 4 5 6 7 8 9\}$, we will end up with $10! = 3,628,800$ rearrangements of the set.
A classic algorithm to generate permutations in lexicographic order is as follows. Consider the list of numbers $s = [1, 2, 3, 4]$. Notice that the sequence is initially sorted. This is required by the algorithm. Now–assuming the indexing of the list is zero-based–we proceed as follows:
-
step 1) Find the largest index $i$ such that $s[i] < s[i + 1]$. If we can't find such an index, it means we are at the last permutation of the sequence:
- From our list, $i = 2$, because the number at index 2, $s[2] = 3$ is less than the number at index $i + 1 = 3$, $s[3] = 4$, and $i = 2$ is the largest index that satisfies this condition.
-
step 2) Find the largest index $j$ that is greater than $i$, such that $s[i] < s[j]$:
- Looking at our list we get $j = 3$. This satisfies our condition $(s[2] = 3) < (s[3] = 4)$
-
step 3) Swap the value of $s[i]$ with that of $s[j]$:
- So, we swap the values at the two indices. Our list becomes: $s = [1, 2, 4, 3]$
-
step 4) Reverse the sequence from $s[i + 1]$ up to and including the last element:
- In our case, $i = 2$. So, the next index $i + 1 = 3$, which is the last index of our list, therefore it stays the same. Our next permutation is $s = [1, 2, 4, 3]$.
We continue this process with the next permutations until the condition $s[i] < s[i + 1]$ is not satisfied. This will indicate that we have reached the last permutation of the sequence.
Finding The Nth Permutation in an Ordered Sequence
The method above generates all the permutations of a set of elements in order. This order is always lexicographic. But, what if we wanted to find the–lexicographically ordered–permutation at an arbitrary position in the sequence? For example, if we wanted to find the 980,000th permutation in the set $\{0 1 2 3 4 5 6 7 8 9\}$? As we mentioned above, we know that there are 3,628,800 permutations in this sequence. Using our previous algorithm, we would have to generate all previous 979,999 permutations before getting to the 980,000th.
For this task, we could use the factorial number system to help us find our arbitrary permutation more efficiently.
The Factorial Number System
The factorial number system or factoradic is a mixed radix numeral system. This means that the radix or base of each digit changes with its position. In contrast, our more familiar numeral systems–such as decimal or binary–keep the base fixed for all digits at each position.
The following table illustrates the factorial number system.
| Radix | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| Place value | 7! | 6! | 5! | 4! | 3! | 2! | 1! | 0! |
| Place value in decimal | 5040 | 720 | 120 | 24 | 6 | 2 | 1 | 1 |
| Highest digit allowed | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
To convert a value from decimal to factoradic, we just need to take the integer division of the value by the radix–starting from 1, 2, 3,... During the successive divisions, we keep track of the remainders–until the division results in 0. The remainder of each division will correspond to the factoradic number digit at that position, going from right to left. For example, to convert 256 (decimal) to factorial number representation:
256 / 1 = 256, remainder 0
256 / 2 = 128, remainder 0
128 / 3 = 42, remainder 2
42 / 4 = 10, remainder 2
10 / 5 = 2, remainder 0
2 / 6 = 0, remainder 2
Arranging the remainders–starting from the bottom and going up–we get the factoradic number: 202200. As an exercise, you can try to convert it back to decimal representation using the table above. We just need to multiply the digit at each position by its corresponding place value and then add them all up.
Using the Factorial Number System to Find the Nth Permutation
We are now ready to use the factorial number system to help us find our arbitrary permutation in the sequence. It turns out there's a relationship between this number system and the lexicographically ordered permutations of a set. This relationship or mapping is known as the Lehmer code.
Now, let's go back to our question of finding the 980,000th permutation in the lexicographically ordered permutations of the set $\{0 1 2 3 4 5 6 7 8 9\}$. As you can see, the set is initially sorted (in non-decreasing order). This represents the lowest permutation of the set. Remember that with this method, we don't need to generate all previous permutations to get to the one we're looking for.
We proceed as follows. First, we are going to assign an index–starting from 0–to all the digits in the set. Initially, index 0 corresponds to digit 0, index 1 to digit 1, and so on, up to index 9 corresponding to digit 9. Also, we will enumerate each permutation in the sequence, starting from 0. So, the initial ordering of the set is permutation number 0. Therefore, we now need to find the $(980,000th - 1) = 979,999th$ permutation.
Now, we take the number 979,999 and start by diving it by $(n - 1)!$ where n is the number of elements in the set–in our case, $n = 10$–so we begin dividing by $9!$ We will keep track of the remainder and the integer quotient:
Initial set: {0 1 2 3 4 5 6 7 8 9}
979,999 / 9! = 2, remainder 254,239
permutation 1st digit: 2
Here, the result of the integer division, 2, indicates the index–inside our set–of the number that corresponds to the first digit in our 979,999th permutation. Index 2 corresponds to number 2. We now take this number out of the set, take the remainder as our new numerator, and continue to the next iteration, subtracting 1 from $n$ in the denominator $(n - 1)!$ We will continue this process until, and including, $(n - 1)! = 0!$:
set: {0 1 3 4 5 6 7 8 9}
254,239 / 8! = 6, remainder 12,319
permutation 2nd digit: 7
set: {0 1 3 4 5 6 8 9}
12,319 / 7! = 2, remainder 2,239
permutation 3rd digit: 3
set: {0 1 4 5 6 8 9}
2,239 / 6! = 3, remainder 79
permutation 4th digit: 5
set: {0 1 4 6 8 9}
79 / 5! = 0, remainder 79
permutation 5th digit: 0
set: {1 4 6 8 9}
79 / 4! = 3, remainder 7
permutation 6th digit: 8
set: {1 4 6 9}
7 / 3! = 1, remainder 1
permutation 7th digit: 4
set: {1 6 9}
1 / 2! = 0, remainder 1
permutation 8th digit: 1
set: {6 9}
1 / 1! = 1, remainder 0
permutation 9th digit: 9
set: {6}
0 / 0! = 0, remainder 0
permutation 10th digit: 6
Putting all digits together, we get: $\{2 7 3 5 0 8 4 1 9 6\}$. This is the 980,000th permutation in lexicographic order of our set.
Notice that the result of each integer division above corresponds to each digit in the factoradic number representation of 979,999 decimal. Putting these digits together gives 2623031010. This is the factorial number representation of 979,999 decimal:
979,999(decimal) = 2623031010(factoradic)
This illustrates the mapping between the factorial number system and lexicographic permutations. And, equivalently, we could've started by converting 979,999–following the procedure in the previous section–to its factorial number representation. Then use each digit in the factoradic number as an index to our shrinking set, as we did above.
Applications of Permutations
In this article, we went from the basic definitions of a permutation to discussing different ways of generating them. We were particularly interested in generating permutations in lexicographic order, and how we can do it efficiently. To finalize, I'll briefly mention some applications of permutations in different areas.
Some of these applications include error detection and correction algorithms in information theory. Permutations are used to analyze sorting algorithms in computer science. They are also used to describe RNA sequences in biology. And, they appear in many branches of mathematics.
Hopefully, this discussion of permutations gave you another perspective and inspired you to continue exploring the subject.
10/11/2021 Correction: the article was updated to fix a typo that said 979,000(decimal) = 2623031010(factoradic). The correct number is 979,999(decimal). Thanks to Joshua F. for pointing this out.