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.
(c) Sven Forstmann
std::string default = "12345";
int perm=1, digits=default.size();
for (int i=1;i<=digits;perm*=i++);
for (int a=0;a<perm;a++)
{
std::string avail=default;
for (int b=digits,div=perm;b>0; b--)
{
div/=b;
int index = (a/div)%b;
printf("%c", avail[index] );
avail[index]=avail[b-1];
}
printf("\n");
}
printf("permutations:%d\n",perm);
/*******************************************/
/* And now the slower but lexigraphic correct version: */
/*******************************************/
std::string default = "12345";
int perm=1, digits=default.size();
for (int i=1;i<=digits;perm*=i++);
for (int a=0;a<perm;a++)
{
std::string avail=default;
for (int b=digits,div=perm;b>0; b--)
{
div/=b;
int index = (a/div)%b;
printf("%c", avail[index] );
avail.erase(index,1) ;
}
printf("\n");
}
printf("permutations:%d\n",perm);
thanks for sharing your code.
but default is a keyword!
you used it as a variable name!
I hardly can imagine a permutation program without recursion (but it is possible).
I have a recursive solution!
>>default is a keyword!
well, the compiler fortunately didnt complain :-)
anyway, the advantage of this implementation over the next_permutation in STL is, that you can instantly get the permutation at any index.
In STL, you need to start at a certain permutation to figure out the next one.
>>well, the compiler fortunately didnt complain :-)
No, in fact thats unfortunate.
>>anyway, the advantage of this implementation over the next_permutation in STL is, that you can instantly get the permutation at any index.
The disadvantages is that this is not a safe code. Its a homemade code,
and is likely to fail at some point with some wrong input. Its not as
efficient as the stl...and much more to list.
Generally, one does this for practice, NOT to replace stl's algorithm.
for the code you just need to write a function with range-checks to return you your desired permutation.
The algorithm used is safe. it computes the order in which you have to remove and print the items of the "avail" array.
It 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.
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;
Not sure if this is published somewhere but it works.
why don't you put your code completely?!
with main() function & headers! so that I can test it with VC++!
Ok, here we go:
#include <string>
int main(int,char**)
{
std::string default_str = "12345";
int perm=1, digits=default_str.size();
for (int i=1;i<=digits;perm*=i++);
for (int a=0;a<perm;a++)
{
std::string avail=default_str;
for (int b=digits,div=perm;b>0; b--)
{
div/=b;
int index = (a/div)%b;
printf("%c", avail[index] );
avail.erase(index,1) ;
}
printf("\n");
}
printf("permutations:%d\n",perm);
while(1);
}yes
it works! thank you!
permutations are sometimes necessary. for example, when you want to have n nested for-loops! where n is variable!
I think your short code is faster than my long recursive one! (I should test it)
And I think you can improve your code. instead of a string use a vector!
:)
Also, your first code showed that in VC++ 'default' can be a variable name! in Borland compilers it can't! perhaps it's a bug for VC!
Good Luck
Hi,
How would you implement that in Cuda?
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.