Algorithm to process all permutions

[PengiunLust]

I think it's strange I have to ask this, because I should know this, but I need an algorithm that will process all the permutations for a set of 6 unique symbols. So if I have A, B, C, D, E, F then I will need to order them as:
A B C D E F
and
A B C D F E
and
A B C F D E
and so on. How can I do that?

[packetpirate]

Do you need to output each permutation? Or just calculate how many there are?

[DSLq5Di1]

http://www.cplusplus.com/reference/algorithm/next_permutation/

[sohguanh]

For professional developers we use pre-built libraries to achieve our objectives but if the OP is doing a tutorial given by his professor I doubt he will allow him to take 'short-cut' although in reality most of us working developers do :P

[PengiunLust]

Thanks, that's perfect.
Actually, this is part of a job interview demo. I think I've got it all licked now.

[PengiunLust]

Oops. It looks like some of the permutations are going to exclude from 1 to 5 elements, meaning I also have to have 5-permutations of 6, 4-permutations of 6, 3-permutions... etc. Is there an algorithm to do that?

[ceruleus]

really sloppy, just threw this together.

        const int num = 5;
	int count = 0;
	int myints[num];
	int currentnum = num;
	for( int x = 0; x < num; x++ )
	{
		for( int i = 0; i < currentnum; i++ )
		{
			myints[i]=i;
		}

		sort( myints, myints+currentnum );

		do{
			for( int i = 0; i < currentnum; i++ )
			{
				cout << myints[i] << " ";
			}
			cout << endl;
			count++;
		} while( next_permutation( myints, myints+currentnum ) );
		cout << count << " permutations so far";
		currentnum--;
		system( "pause" );
	}

	cout << "\n Total of " << count << " permutations!";

	system( "pause" );
	return 0;

system( "pause" ); FTW!!!!!

[PengiunLust]

FTW?
I don't think this is it, because it seems that you just have 5-permutations of 5 then 4-permutations of 4 then 3 of 3, etc. Notice that in your output 4 disappears after you output sets of 5, and then 3 disappears after outputting sets of 4, and so on. The correct behavior of this would have that all numbers, 0 through 5, would make an appearance with each iteration of the outer loop.
But ya know what: it doesn't actually matter. With every permutation, I can check to see if I've found success when I process each element. Yes, that'll make for a ton of redundant tests, but I think I'm past caring about that.

[sohguanh]

Just curious to know. The job interview demo is to show them a working program to do that or you can verbally write out pseudo-code to let them see?

Based on experience, pseudo-code is very useful but it is not 100% as during implementation due to programming language constraints or quirk behavoir, you need to do extra lines of coding to complete the pseudo-code you have written earlier.

It is often said once you have the pseudo-code, you have the program already. Well the mapping process isn't that straight-forward and a lot of times developers under-estimated the man-days effort on the implementation besides the man-days effort spent on the pseudo-code design. The devil is always in the details I would say.

Just to add on, in the business world, end users are going to use the implementation to make monies and not your grand pseudo-code design written on paper or notepad or whatever :)

[PengiunLust]

I believe they called for a program, but not specifically a permutations algorithm--that's just a means to an end.

[ceruleus]

PenguinLust - I see what you're saying now... my bad.

[PengiunLust]

Dammit! I thought about it some more and my idea that makes that more specific permutation calculation unnecessary is wrong. So now I need an algorithm that processes k-permutations of n. Please help.