Ideas on how to create a function which outputs all the possible permutations of a given number N...

[imhotepmp]

I want to create a function that can output all the possible permutations of a given number n.
For example, suppose we have n=3 numbers:1, 2, 3
the # of permutations would be n! in this case 3!=6
the permutations would be: 123,132,213,231,321,312

Any ideas on how to create an algorithm to do this. Im thinking you would need recursion to implement this. But what would be the stopping case since you dont want infinite recursion.

MODS: ive seen several threads which discuss mathematical theories, so I thought this foum would be more appropriate than the prog forum. If you think otherwise, feel free to move it(as if you needed my permission )

thanks for all responses.

Imhotep MP

 

[Viper GTS]

Never mind, I mis-read your question...

Viper GTS

 

[crypticlogin]

I think this would be a straight up recursion program, but I'm a little unclear as to what you mean by "n" numbers (digits? consecutives? countings? a set of numbers with 'n' members?).

But otherwise, your program would take each number in the set, then recursively rearrange all of the remaining numbers until the there are no more numbers in the set. You did this mentally when writing out your example sequence so I think you have the idea.

 

[lnvictus]

So you want, say, a number, and that number represents the numbers in the set, 1 to n, and then you want all the ways you can arrange all the numbers in the set without producing a duplicate number? so if n = 4 then you want 24
1234 1243 2143 1324 1342 4123 etc. etc. with no repeats...?

What are you looking for? The number of times you can do that? Or all of the numbers that can be made from it?

If you want the number of times you can do that, that's a factorial (which you knew)
But if you want all the numbers, that's recursion. I can't think of a stopping point either...

I'm still not clear on what you want from this function though...

 

[imhotepmp]

<< So you want, say, a number, and that number represents the numbers in the set, 1 to n, and then you want all the ways you can arrange all the numbers in the set without producing a duplicate number? >>



Yes, but i dont want the number itself, rather i want to OUTPUT ALL of the possible combinations.



<< I'm still not clear on what you want from this function though... >>




The function itslef would print out all the permutations.
For example if the function prototype looked like this:

permutation(int n)

and n=2 it would print "12 21"
n=3 it would print "123 132 213 231 321 312"

Imhotep MP

 

[blahblah99]

a quick and dirty way to do it is to make an array the size of possible permutations. then pick a random number between 1 and n, assign it to first position, pick another random number, assign it to the second position, etc etc until the nth number is assigned to the nth position. check if that newly created number is in the array, if not, insert it into the array and run the random thingy again. Keep have it loop until you fill up the array. then do a bubblesort or watevers if you want it nice and clean .

Of course, this way is very crude and would only work for small n's

 

[Sir Fredrick]

Ok, I'm not sure if this would actually work, but I think it's close.
I'm using some global variables which is not good, and the size of the array is not set. This will probably produce redundant entries in final[], so it can't just be n! size.
This implementation assumes that you have a function called swap(int x, int y, string str) which swaps the characters in a string and then returns the new string.

I'm at my girlfriend's right now, so I can't run this through the compiler to see what happens, but it should work after a few minor adjustments. There's probably a more efficient way to do this, but I just whipped it up in 3 minutes...

string original = "1234";
string final[];
int f = 0;
string str = swap(0,1,original)
findallpermutations(str);

findallpermutations(string st){
if (st == original)
return;
for(int i = 0; i<st.strlen();i++){
st = swap(i,i+1, st);
final[f++] = st;
findallpermutations(st);
}
return;

}

 

[lnvictus]

ok i think i got it..
you input the #, find the factorial of it, and then make an array of structures (see bottom) of size n!

then you write a recursive function, the quit case will be when g > n
note: i'm in high school so i'm used to apvectors and such for arrays, this is in C++
so say n is 4, N! = 24, so you have an array of 24 strings, start each string at "" so when you add something it doesn't mess up...
divide N! by N (6) then fill that many boxes with g (g is the current number you're at) so the first six boxes in the array would have "1" in them. then on the next turn you divide the number of boxes you're working (6) with by the number of numbers remaining to be used (3) and then you will that many boxes (2) with the numbers remaining. so your array looks like this: 12 12 13 13 14 14
then, you recurse again, and divide the # of boxes you're working with (2) by the number of numbers remaining (2) and you fill that many boxes (1) with the next number, and keep doing that and now your array looks like this: 123 124 132 134 142 143
then add the remaining number to the end of the string. this would probably work best with a structure of a string and 4 booleans
edit: oh yeah, keep doing all this with 2, 3, 4 as the starting numbers, and recurse and recurse and blah blah blah I WISH I HAD MY C++ compiler so I could check this...

here's the structure i was talking about..
struct perm
{ apstring number;
apvector <bool> used;
}

resize that vector to 5 (there's 5 because 0 is a thing in C++, so it goes from 0-4), set them all false, and when you use that number mark it true so you don't put it again.


i think i got it, but probably not...

 

[br0wn]

The following function will display all permutation
of the elements of array A, where n is size of array A.

void permute_list(int A[ ], int num, int n)
{
int i,j,temp, k;
int start = n - num + 1;

if( num == 1 )
{
for(k = 0; k < n; k++)
cout << A[ k ] << " ";

cout << endl;
return;
}

for(i = start; i < n; i++)
{
permute_list(A,num-1,n);

/* rotate the list */
temp = A[ n-1 ];
for( j = n-1; j > start; j-- )
A[ j ] = A[ j-1 ];

A[ start ] = temp;
}
}

You can initialize array A by the following code:

for (i=0; i<n; i++)
A[ i ] = i;

permute_list(A, n+1 , n);

 

[wesman]

For some reason my brain got caught on this little exercise, I like recursion even though it gives me a headache....

so I started looking for patterns


3 x=1 2 3

y=1 123 213 321
2 132 231 312


4 x=1 2 3 4

y=1 1234 2134 3214 4231
2 1243 2143 3241 4213
3 1324 2341 3124 4321
4 1342 2314 3142 4312
5 1423 2413 3421 4123
6 1432 2431 3412 4132


for N!, x=N and Y=(N-1)!

You may also notice that strings(1, 1 to N) equal "1" + "{array(N-1)}+1"

3 x=1

y=1 123 ="1" + ({12}+1) ="1"+"23"
2 132 ="1" + ({21}+1) ="1"+"32"


4 x=1

y=1 1234 ="1" + ({123}+1) ="1"+"234"
2 1243 ="1" + ({132}+1) ="1"+"243"
3 1324 ="1" + ({213}+1) ="1"+"324"
4 1342 ="1" + ({231}+1) ="1"+"342"
5 1423 ="1" + ({312}+1) ="1"+"423"
6 1432 ="1" + ({321}+1) ="1"+"432"

This part would be easy to implement recursively.


once we have the first row it's easy to generate the rest:


for a=1 to y
for b=2 to x
string(b,a)=swap(1,b,string(1,a))


I wrote all this before the previous post, didn't want it to go to waste, not that it won't anyway...



EDIT: format all messed up don't know what I can do about that, and the site is slowing to a crawl for me so lets hope this edit goes thru (second time trying)....sorry