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.

Permutations in C++, Part 2

Now, find the second element from the remaining elements (0,1,2,4),

0,1,2,4 = factorial(3) * 0 = 0th Permutation
0,x,x,x
.
.
0,x,x,x
1,0,2,4 = factorial(3) * 1 = 6th Permutation
1,x,x,x
.
.
1,x,x,x
2,0,1,4 = factorial(3) * 2 = 12th Permutation
2,x,x,x
.
.
2,x,x,x
4,0,1,2 = factorial(3) * 3 = 18th Permutation
4,x,x,x
.
.
4,2,1,0 = Last permutation(23th)
x,x,x,x = factorial(3) * 4 = 24th Permutation (out of bounds)

As you can see, 7 is sandwiched between the 6th and 12th permutations, so the 2nd element is 1. Subtract 6 from 7, which leaves 1.

Let the next iteration begin:

0,2,4 = factorial(2) * 0 = 0th Permutation
0,x,x
2,0,4 = factorial(2) * 1 = 2nd Permutation
2,x,x
4,0,2 = factorial(2) * 2 = 4th Permutation
4,2,0 = Last permutation(5th)
x,x,x = factorial(2) * 3 = 6th Permutation (out of bounds)

As you can see, 1 is sandwiched between the 0th and 2nd permutations, so the 3rd element is 0. There is nothing to subtract in this iteration.

2,4 = factorial(1) * 0 = 0th Permutation
4,2 = factorial(1) * 1 = 1st Permutation

As you can see, 1 is equal to 1st, so the 4th element is 4. There is no need for the next iteration because only two are left, so the 5th element is 2.

The generated permutation is 3,1,0,4,2 for index 79. You can verify this by calling next_permutation() 78 times. It is 78 times because the first permutation 0,1,2,3,4 is not generated by next_permutation() but rather fed into next_permutation(). As you may have noticed, the last permutation is always in descending order.

Can you reverse-engineer 3,1,0,4,2 and get the index 79? Sure; just follow these steps:

  1. Remove 3 from the 0,1,2,3,4; it turns into 0,1,2,4.
  2. Factorial(4) * IndexOf(3) in {0,1,2,3,4} = 4! * 3 = 72
  3. Remove 1 from the 0,1,2,4, it turns into 0,2,4
  4. Factorial(3) * IndexOf(1) in {0,1,2,4} = 3! * 1 = 6
  5. Remove 0 from the 0,2,4, it turns into 2,4
  6. Factorial(2) * IndexOf(0) in {0,2,4} = 2! * 0 = 0
  7. Remove 4 from the 2,4, it turns into 2
  8. Factorial(1) * IndexOf(4) in {2,4} = 1! * 1 = 1
  9. Add up all the calculations, you will get 72 + 6 + 0 + 1 + 0 = 79
  10. Factorial(0) * IndexOf(2) in {2} = 1! * 0 = 0

Permutations in C++, Part 2

Code examples for Finding Permutations By Index (Factoradic)

#include <iostream>
#include "Factorial.h"
#include "FindPermByIdx.h"

void main()
{
   const int SIZE = 3;

   // Initialize the factorial class of 100 factorial: it is optional
   // It would be faster if you need to call FindPerm() many times
   // If you don't initialize this class, each factorial have to be
   // calculated each time it is needed.
   // CFactorial<BigInteger>::Init();

   CFindPermByIdx<BigInteger> findperm;

   BigInteger biResults;
   // Initialize the first permutation
   vector<unsigned int> vec(SIZE);
   vec[0]=0;
   vec[1]=1;
   vec[2]=2;

   int cnt = 0;
   bool bContinue=true;
   // Display the first permutation
   {
      cout<<cnt<<")";
      ++cnt;
      for( int j=0; j<SIZE; ++j )
      {
         cout<< vec[j] << ",";
      }
      
      cout<<endl;
   }
   do
   {
      // Find the permutation, given its index(cnt)
      bContinue = findperm.FindPerm( SIZE, cnt, vec );

      if( bContinue )
      {
         // Display the results
         cout<<cnt<<")";
         for( int j=0; j<SIZE; ++j )
         {
            cout<< vec[j] << ",";
         }
      }
      
      cout<<endl;

      ++cnt;
   }
   while( bContinue );

   // If you have called CFactorial::Init();, you must call its
   // Destroy()
   CFactorial<BigInteger>::Destroy();
   
}

You may have noticed that CFindPermByIdx operates on numbers only and the contents of first permutation vector is always starts from zero and is in running numbers. Unlike next_permutation(), which operates on objects by comparing, CFindPermByIdx operates on zero-based running numbers. What you will get from its results are indexes. For example, if you get a result of {0,2,1}, it means the 1st element is index 0 of an array (of objects) you originally want to permute, the 2nd element refers to index 2 of the array, and the 3rd element is index 1 of the array. Permuting numbers is much easier and faster than permuting objects. CFindPermByIdx uses a big integer class because this algorithm uses factorials to find the permutation and factorials are usually very large numbers. Because it is a templated class and you know the factorials used are not going to exceeded 64 bit, you can use the __int64 type instead. The is the output of the above example code.

0)0,1,2,
1)0,2,1,
2)1,0,2,
3)1,2,0,
4)2,0,1,
5)2,1,0,

Benchmark Between next_permutation() and CFindPermByIdx

Below is the timing results of next_permutation() and CFindPermByIdx finding permutations of eight elements, which is 40320 permutations in total.

time taken for next_permutation: 1 milliseconds
time taken for CFindPermByIdx: 3915 milliseconds

The source code for the benchmark is included for download.

Permutations in C++, Part 2

Code Examples for Finding Index from a Permutation

#include <iostream>
#include "Factorial.h"
#include "FindPermByIdx.h"

void main()
{
   const int SIZE = 4;

   // Initialize the factorial class of 100 factorial: it is optional
   // It would be faster if you need to call FindIndex() many times
   // If you don't initialize this class, each factorial have to be
   // calculated each time it is needed.
   CFactorial<BigInteger>::Init();

   CFindPermByIdx<BigInteger> findperm;

   BigInteger biResults;
   // Initialize the first permutation
   vector<unsigned int> vec(SIZE);
   vec[0]=0;
   vec[1]=1;
   vec[2]=2;
   vec[3]=3;

   do
   {
      // find the index of this permutation
      findperm.FindIndex( 4, biResults, vec );

      // Display the results
      cout<<biResults<<")";
      for( int j=0; j<SIZE; ++j )
      {
         cout<< vec[j] << ",";
      }

      cout<<endl;
   }
   while( next_permutation( vec.begin(), vec.end() ) );

   // If you have called CFactorial::Init();, you must call its
   // Destroy()
   CFactorial<BigInteger>::Destroy();
}

The is the output of the above example code.

0.)0,1,2,3,
1.)0,1,3,2,
2.)0,2,1,3,
3.)0,2,3,1,
4.)0,3,1,2,
5.)0,3,2,1,
6.)1,0,2,3,
7.)1,0,3,2,
8.)1,2,0,3,
9.)1,2,3,0,
10.)1,3,0,2,
11.)1,3,2,0,
12.)2,0,1,3,
13.)2,0,3,1,
14.)2,1,0,3,
15.)2,1,3,0,
16.)2,3,0,1,
17.)2,3,1,0,
18.)3,0,1,2,
19.)3,0,2,1,
20.)3,1,0,2,
21.)3,1,2,0,
22.)3,2,0,1,
23.)3,2,1,0,

A Benchmark Program for Your PC

I have included a demo program, called TimePermutations, for you to benchmark your PC. It is nice to know how much time have been reduced if you have a dual-core or quad-core PC. The program does not store the permutation anywhere and discards it after every computation. If you have a uniprocessor PC, you have little much use for this benchmark program. Below are the screenshots of the program.

[TimePerm.PNG]
[TimePermResults1.PNG]
[TimePermResults2.PNG]

Conclusion

In this article, I have introduced an algorithm, called "finding permutations by index" or factoradic, to let you find the nth permutation and continue it from there with next_permutation() to split and speed up the work on many processors. I look forward to your feedback on the article! Hope you like my article!

References

History

  • 12 Mar 2009 - Changed the source code to use C++ Big Integer Library written by Matt McCutchen, so as to remove the need to download and build Crypto++, and also to reduce download sizes.
  • 19 Nov 2007 -- Original version posted


About the Author

Wong Shao Voon

I guess I'll write here what I does in my free time, than to write an accolade of skills which I currently possess. I believe the things I does in my free time, say more about me.

When I am not working, I like to watch Japanese anime. I am also writing some movie script, hoping to see my own movie on the big screen one day.

I like to jog because it makes me feel good, having done something meaningful in the morning before the day starts.

I also writes articles for CodeGuru; I have a few ideas to write about but never get around writing because of hectic schedule.

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • IBM Worklight is a mobile application development platform that lets you extend your business to mobile devices. It is designed to provide an open, comprehensive platform to build, run and manage HTML5, hybrid and native mobile apps.

  • On-demand Event Event Date: October 29, 2014 It's well understood how critical version control is for code. However, its importance to DevOps isn't always recognized. The 2014 DevOps Survey of Practice shows that one of the key predictors of DevOps success is putting all production environment artifacts into version control. In this webcast, Gene Kim discusses these survey findings and shares woeful tales of artifact management gone wrong! Gene also shares examples of how high-performing DevOps …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds