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
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.
:confused:
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 class :)Quote:
something 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.Quote:
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?