Permutations Utilizing STL Vectors and Recursion using Steinhaus Algorithm

• Download source - 5.09 KB

Introduction

This is a namespace with classes and functions to generate permutations of numbers without repetition utilizing STL vectors and recursion. 

While investigating how to create combinations (see my previous article), I came up to an algorithm (here) created by Hugo Steinhaus (January 1887-February 1972), a student of  David Hilbert at Göttingen. 

Background 

This code is one of the several exercises I am doing in order to learn STL.

The algorithm is in fact so simple that I wonder why nobody thought about it before Mr. Hugo.  It goes like this:

The minimum set of numbers possible that allow to create a permutation is: 1,2.

Given these two numbers, let's create all the possible permutations with no repetition. The result is:

1,2
2,1    

Based on this simple matrix, we will increase its dimension so that the resulting matrix containing the permutations will be a matrix compound of repetitions of the previous matrix, with a 'weaved' number index n, starting from the right (last index) and when the index becomes 0, go to the next row and start again.

To see the case n = 3, the idea is to (a) write down each row  n = 3 times each as follows:

1 2 
1 2    
1 2   
2 1  
2 1  
2 1  

... then we "weave" in a 3 as follows:  

1 2 3 
1 3 2  
3 1 2 
2 1 3 
2 3 1 
3 2 1  

These resulting numbers can be used as indexes for the input numbers you might have.

Using the Code  

I created a templatized class called Vector that holds two vectors as member variables:

• one vector to store the resulting rows of numbers, and 
• another vector to store the resulting vectors (vector of vectors)  

The process consists of three steps:

1. Set size row number size
2. Initiate the process by creating our first matrix of 2 x 2
3. Weave the necessary numbers in our already created rows.

These three steps are mapped 1 to 1 in the class' member functions:

void SetMax(const unsigned int Max) ; 

void InitProcess(); 

void Iterate(unsigned int iteration);

The interesting part is in the function Iterate. Here is where we implement the Steinhaus algorithm:

    void Iterate(unsigned int iteration)
    {
            VecVec localVec;
            for(typename VecVec::iterator it = eelems.begin(); it!= eelems.end();it++)
                {
                (*it).push_back(iteration);
                size_t size = (*it).size();
                for (unsigned int x = 0; x < iteration; x++)
                    {
                    localVec.push_back(*it);
                    if (size-1 < 1)
                        break;
                    swap((*it)[size-2], (*it)[size-1]);
                    --size;
                    }
                }
            eelems = localVec;

            if (iteration < max)
                Iterate(++iteration);
            else
                return;
    }

 At the end of the process, we use the static templatized function Burp to send the results to STDOUT the resulting vector of vectors, utilizing an algorithm:  

// displays results after processing is done
template <typename T>
void Burp(ostream& os, vector< vector<T> >& vec)
    {
    os << "Our vector of vectors" << endl;
    for(typename vector< vector<T> >::iterator it = vec.begin(); it!= vec.end();it++)
        {
        copy((*it).begin(), (*it).end(), ostream_iterator<unsigned int>(os, " "));
        os << endl;
        }
    os << "/Our vector of vectors" << endl;
    }

Points of Interest

The usage of vectors was interesting for me. I could have used some other type of array, like for example, an array of ints, but the fact that we can templatize the vector, the functions to access and modify the data it contains, and the fact that it is just as fast as using an array, made it very appealing for me.

I have included a Microsoft VS 2005 project that also contains (within the comments) the command line to compile it using g++ on Cygwin.  

Conclusion

I compiled on Microsoft VS 2005 and executed the resulting program on a DOS window and on an XTERM on Cygwin. The same program executed faster on the Cygwin window!
I compiled the program using g++, and the program runs even faster.

I had some problems with the Microsoft Compiler (no surprises here) that made me waste time; however, a reasonable approach for every programmer would be to compile his/her code in more than one compiler, some errors and warnings are not displayed in some compilers.

History 

• Version 1