Generating 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++);
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]; // non-lexigraphic but fast
		avail.erase(index,1) ; // lexigraphically correct
	}
	printf("\n");
}
printf("permutations:%d\n",perm);

(c) Sven Forstmann

[m4ster r0shi]

And just when I needed something like this... the non-lexigraphically correct method is it like in linear time?

[m4ster r0shi]

lol, forget it, stupid question... since you get ALL permutations it can't be linear time :P Or... can it?

[spacerat]

Yes, you can generate one single permutation in linear time - O( n ), where n is the string length. All permutations take n*(n!) because you have to print at least each character.

[m4ster r0shi]

ok then, I ll take it :D I want it for a random number generator I m making, take a look if you want :P
http://www.cplusplus.com/forum/beginner/21804/page2.html#msg114576