All Permutations - non-recursive

[spacerat]

The other code snipplets I found were either recursive or too complex.
I therefore developed a simple, fast and yet non-recursive method;
thats useful especially when working on the graphics card with CUDA as recursion is not possible there.

std::string default = "12345";
 
int perm=1, digits=default.size();
for (int i=1;i<=digits;perm*=i++); // perm = !default.size()
for (int a=0;a<perm;a++)
{
    std::string avail=default; // initialize string
 
    // b counts the columns
    for (int b=digits,div=perm;b>0; b--) 
    {
        // compute the number of repetitions for one character in the actual column
        div/=b;
        //compute the index of the character in the string 
        int index = (a/div)%b;       
        printf("%c", avail[index] );
        //remove the used character
        avail.erase(index,1) ;
    }
    printf("\n");
}
printf("permutations:%d\n",perm);

(c) Sven Forstmann

[donbock]

Do you have a question?

It looks like your first loop computes factorial(digits) in an int variable. A 16-bit int can hold at most 8!; a 32-bit int can hold at most 12! Are these limits acceptable for how you intend to use this program?

[jkmyoung]

div is not defined, and if this is meant to be an insight, there should be comments in the code.

[spacerat]

@donbock: To get more digits, you have to use a 64 bit integer or write an extension for 128 and more bits, as it is done for public key encryption e.g.

At the moment I dont have any plans for the program - it was just written for experimental purpose.

The algorithm is based on the following property. Lets say you have 6 characters in the string that you want to permute. Then you get 6! = 720 combinations. In the first column of your results, you get 720/6=120 lines of each character. This means if your index counts from 0 to 719, then the first character to be removed is computed as remove_index = index/120.

For the next column, you have 5 numbers left. This means, that 120 = 5 * 24 lines of the same character - and so on. Its not based on a random thought as you might think.

You get the following list:
column0: remove_index = (a/120)%5;
column1: remove_index = (a/24)%4;
column2: remove_index = (a/6)%3;
column3: remove_index = (a/2)%2;
column4: remove_index = (a/1)%1;

Do you know if this is written in a paper somewhere?

[spacerat]

@ jkmyoung:
div is defined in the beginning of the for loop.
for (int b=digits,div=perm;b>0; b--)

>>there should be comments in the code.
done

[jkmyoung]

I meant the type has not been defined. If you're going to post this code, at least post fully compiling code. This algorithm doesn't deal with duplicates then?

It is interesting in that the combined index a is like a number with multiple bases:
(From the right) the first digit is base 1, the second digit is base 2, the third digit is base 3,
(5*4*3*2), (4*3*2), (3*2), 2, 1
24, 6, 2, 1
etc...

So the index values are 43210
Which means pick the 5th char of the 5 characters, (since 4 is the index of the 5th element)
then pick the 4th char of the remaining 4
then pick the 3rd of the remaing 3
then pick the 2nd of the remaining 2
then pick the last one.

So if we pick a random number less than 120, say 75, and convert it into the multiple bases we get:
3011
Which means pick the 4th 4, leaving us with 1235
pick the 1st, 1, leaving us with 235
pick the 2nd, 3, leaving us with 25
pick the 2nd, 5, leaving us with 2

41352 is the 76th number printed by this program.
===
Criticisms:
copying the string and then truncating over and over may affect efficiency.
===
I think this problem is slightly more useful: http://uva.onlinejudge.org/index.php...lem&problem=82
If you come up with a solution to this problem, you can easily modify the program, loop and print all iterations. (Plus, you can make smart optimizations.).

Dealing with the duplicates makes it a little more complicated, so don't know if that's what you need.
=====

[spacerat]

>>I meant the type has not been defined.

It should be defined - its same as defining multiple ints with int a=1,b=2,c=2; Isn't it?

>>I think this problem is slightly more useful: http://uva.onlinejudg..

Hm.. looks to me like they want the next_permutation function of STL - or am I wrong? (link to the STL source)

>>Criticisms: copying the string and then truncating over and over may affect efficiency.

Yes, thats a bit slow. You can make it faster but then its in non-lexigraphic order: replace avail.erase(index,1) ; by avail[index]=avail[b-1];. The algorithm is not the fastest to get all permutations at once - but its very efficient if you want the n'th permutation in particular.