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

Printable View

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

You header might look like:

Code:`void func (char *str, int position)`

Code:`func(str, position+1);`

Code:`char *ptr = malloc(n + 1);`

ptr[n] = '\0';

func(ptr, 0);

free(ptr);

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

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

- 05-29-2005packer
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-2005Thantos
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-2005dwksQuote:

Code:`void perm(int n,int array[]){`

/* ... */

printf("%d ", array);

- 06-01-2005packerpermutations
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");

}

}

- 06-01-2005xErath
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-2005packer
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-2005Thantos
Threads merged. In the future please keep to one thread for the same problem.

- 06-02-2005packer
ok sorry...so any suggestions?