any ideas of how to print the permutations from 1 to n?
if n=4
permutations of 1 2 3 4
1 3 2 4
2 3 1 4 ....and so on
any ideas of how to print the permutations from 1 to n?
if n=4
permutations of 1 2 3 4
1 3 2 4
2 3 1 4 ....and so on
use recursion and an array of characters passed into the function.
You header might look like:
your recursive call would look something likeCode:void func (char *str, int position)
and the inital code might look something like:Code:func(str, position+1);
Code:char *ptr = malloc(n + 1); ptr[n] = '\0'; func(ptr, 0); free(ptr);
If it is homework then my bad, although there was no indication and something like a permutation generator seems a little difficult for a general comp sci course, so I just thought he was doing it for his own purposes - perhaps trying to develop an anagram solver???
Anyway no bother, its c++ so it hardly matters.
Last edited by treenef; 05-29-2005 at 02:10 PM.
Treenef don't do other people's homework. And second thats C++ in a C board.
thantos, thanks you have been lots of help, but could you give me an idea of how it should be implenented?
i cant seem to figure out how to permute the numbers, i tried printing first the 1 and then permute 2, 3,...n but seems to complicated
please help
Lets say you had to list the ones for n = 3 you have
123
132
213
231
312
321
How did I come up with that list?
Well I looped the first digit from 1-3
Each time I went onto the second digit and looped from 1-3, skipping any numbers already in use
During each iteration of the second number I went to the third and iterated that from 1-3 skipping the ones that were in use already
Now you might need to pass more information to the function then I said earlier, thats for you to determine.
This is probably not the faster method but its easy to implement and works well for smaller values of n ( < 100 or so)
I had to do this same problem in my assembly classsomething like a permutation generator seems a little difficult for a general comp sci course
this is what i have so far, i cant seem to figure out the printing of the permutations or correct me if anything is wrong
Code:#include<stdio.h> void perm(int n,int array[]){ int i,j; printf("%d ", array); if(array==0 || array==1){ printf("no permutations can be done with 0 or 1\n"); }else { for(i=0;i<=n;i++){ j=array[i]; perm(n,array[i+1]); printf("%d %d",j,array[i+1]); } } } main(){ int n,i,k; int array[15]; scanf("%d", &n); for(i=1;i<=n;i++){ array[i]=i; printf("%d ", array[i]); } perm(n,array); printf(" \n"); }
Heres an example that will print out all combinations. It'll be your job to figure out how to remove the unneeded ones:
Code:void perm (int n, char *arr, int depth) { int i; if ( depth == n ) { puts(arr); return; } for(i=0; i < n; i++) { arr[depth] = '0' + i + 1; perm(n, arr, depth+1); } } int main() { int n; char *ptr; n = 5; ptr = malloc(n+1); ptr[n] = '\0'; perm(n, ptr, 0); return 0; }
Opps.Code:void perm(int n,int array[]){ /* ... */ printf("%d ", array);
i have to create the permutations from the numbers 1 ....n but i cant seem to werk out the recursion part.
note. i should not use pointers or strings, just plain simple C with an array from 1 to n
here is my code that i have so far, when i compile it lets me input n but then it results in a segmentation fault
any suggestions on how to make it better or is my algorithm totally incorrect???Code:#include<stdio.h> void print(int array[],int n){ int i; for(i=0;i<=n;i++){ printf("%d ", array[i]); } } void perm(int n){ int i,j,x,y; int arreglo[15],array[15],pos[15]; perm( n+1 ); for (i=1; i <= n-1; i++) { j = array[n]; x = j + pos[n]; y = array[x]; arreglo[j] = y; arreglo[x] = n; array[y] = j; array[n] = x; perm(n-1); print(array,n); } } int getn(){ int n; scanf("%d",&n); if(n>1){ return n; }else { return 0; } } main(){ int x; x = getn(); if(x>1){ perm(x); printf(" \n"); }else { printf(" el numero debe ser mayor a 1\n"); } }
in the function perm.. if 'n' is 15 of greater, array[n] will be out of bounds. therefore you'll get an undefined behaviour which could be writing on another array, or non-owned memory, which results in a segmentation fault.
So your program will always crash because perm(1) will call first perm(2), which will call perm(3) and so on without stoping, which includes calling perm with a value equal or greater than 15. Also that recursive call has no restriction, which will blow the process stack.
Code:oid perm(int n){ int i,j,x,y; int arreglo[15],array[15],pos[15]; perm( n+1 ); //recursive call without any control or restriction for (i=1; i <= n-1; i++) { j = array[n]; x = j + pos[n]; y = array[x]; arreglo[j] = y; arreglo[x] = n; array[y] = j; array[n] = x; perm(n-1); print(array,n); } }
ok thanks, i fixed that, i think that my recursion call is not correct, i think my algorith is pretty bad, could you help me out?
Threads merged. In the future please keep to one thread for the same problem.
ok sorry...so any suggestions?