Permutations in C++, Part 2

Introduction

In the coming years, multi-core processors will become the mainstream. It would be nice to have a dual-core CPU; you could use each core to compute 50% of the total permutations. However, next_permutation in the STL’s algorithms does not let you do so. Why? The reason is that the next_permutation relies on the current permutation to generate the next one.

Consider this situation: You have a total of 200,000,000 permutations to find. If you can find the 100,000,000th permutation, you can use two threads calling next_permutation() 100,000,000 times; 1 thread will start from 0th permutation and the other will start from 100,000,000th permutation.

However, to find the 100,000,000th permutation, you have to call next_permutation() 100,000,000 times! Hence, I have created an algorithm that lets you compute the 100,000,000th permutation. This method is called “finding the permutation by index” or “positional permutations.” Update: I found out that this method has been invented for quite some time and its actual name is called factoradic. This method is to be used in conjunction with next_permutation() to spread the workload among different cores or SMP processors. Of course, factoradic can be used to find all the 200,000,000 permutations, but because next_permutation() is much faster than the factoradic implementation, you only use factoradic to find the nth permutation and from the nth permutation onwards, you are going to use next_permutation() all the way.

The Technique of Finding Permutations

Do a quick runthrough on how to find permutations before I show you how to find a permutation, given its index. I will show you an example of finding the permutation of 0,1,2,3.

In the first column, write down these numbers:

0,
1,
2,
3,

For the first column, each number is going to have 3! rows because there are three other unwritten columns.

0,
0,
0,
0,
0,
0,

1,
1,
1,
1,
1,
1,

2,
2,
2,
2,
2,
2,

3,
3,
3,
3,
3,
3,

For the first column, you will find the permutations of the number 0. You will ignore 1, 2, and 3 for time being. For the second column, each number is going to have 2! rows because there are two other unwritten columns.

0,1,
0,1,
0,2,
0,2,
0,3,
0,3,

For the last two columns, write down the numbers that are not taken by the 1st and 2nd columns in ascending order, and the next row in descending order.

0,1,2,3
0,1,3,2
0,2,1,3
0,2,3,1
0,3,1,2
0,3,2,1

By using the same method, you can find permutations for the other three numbers—1,2,3—in the first column, All the permutations are shown below.

0,1,2,3
0,1,3,2
0,2,1,3
0,2,3,1
0,3,1,2
0,3,2,1

1,0,2,3
1,0,3,2
1,2,0,3
1,2,3,0
1,3,0,2
1,3,2,0

2,0,1,3
2,0,3,1
2,1,0,3
2,1,3,0
2,3,0,1
2,3,1,0

3,0,1,2
3,0,2,1
3,1,0,2
3,1,2,0
3,2,0,1
3,2,1,0

The Technique of Finding a Permutation, Given the Index

Note: The total number of permutations is a result of taking the factorial of the total number of elements.

To explain the algorithm, let me take you through the steps of an example.

Given the index 79, you need to find the permutation from a set of five elements, 0,1,2,3,4. The total permutations is 120. Because this technique is zero-based, the last index would be the 119th.

Begin by finding the element in Column 1 (columns are one-based).

0,1,2,3,4 = factorial(4) * 0 = 0th Permutation
0,x,x,x,x
.
.
0,x,x,x,x
1,0,2,3,4 = factorial(4) * 1 = 24th Permutation
1,x,x,x,x
.
.
1,x,x,x,x
2,0,1,3,4 = factorial(4) * 2 = 48th Permutation
2,x,x,x,x
.
.
2,x,x,x,x
3,0,1,2,4 = factorial(4) * 3 = 72th Permutation
3,x,x,x,x
.
.
3,x,x,x,x
4,0,1,2,3 = factorial(4) * 4 = 96th Permutation
4,x,x,x,x
.
.
4,3,2,1,0 = Last permutation(119th)
x,x,x,x,x = factorial(4) * 5 = 120th Permutation (out of bounds)

To find the 1st element, you need to find in the positional permutations which 79 is greater than and yet smaller than or equal to the next positional permutation. As you can see, 79 is sandwiched between 72 and 96; the 5th element is 3. As for why factorial(4), it is because you are finding one element out of five elements now. Subtract 1 from 5 elements and you get 4. Let me give an example to clarify: To get from 0,1,2,3,4(0th Permutation) to the 1,0,2,3,4(24th Permutation), column 2 to column 5 would have permute 4!-1 times because there are four columns to permute. Before you proceed to find the second element, you need to subtract 72 from 79, which is 7, before proceeding to the next iteration.

More by Author

Previous articleDistributed Network Object
Next articlePartial Methods

Must Read