# permutations

• 05-28-2005
packer
recursion+permutations
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
• 05-28-2005
Thantos
use recursion and an array of characters passed into the function.

You header might look like:
Code:

`void func (char *str, int position)`
your recursive call would look something like
Code:

`func(str, position+1);`
and the inital code might look something like:
Code:

```char *ptr = malloc(n + 1); ptr[n] = '\0'; func(ptr, 0); free(ptr);```
• 05-29-2005
treenef
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.

:confused:
• 05-29-2005
Thantos
Treenef don't do other people's homework. And second thats C++ in a C board.
• 05-29-2005
packer
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

• 05-29-2005
Thantos
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)

Quote:

something like a permutation generator seems a little difficult for a general comp sci course
I had to do this same problem in my assembly class :)
• 05-29-2005
packer
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");         }```
• 05-29-2005
Thantos
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; }```
• 05-31-2005
dwks
Quote:

Code:

```void perm(int n,int array[]){ /* ... */     printf("%d ", array);```

Opps.
• 06-01-2005
packer
permutations
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

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");         } }```
any suggestions on how to make it better or is my algorithm totally incorrect???
• 06-01-2005
xErath
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);         } }```
• 06-01-2005
packer
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?
• 06-01-2005
Thantos
Threads merged. In the future please keep to one thread for the same problem.
• 06-02-2005
packer
ok sorry...so any suggestions?