Thread: permutations

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    18

    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

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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);

  3. #3
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    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 01:10 PM.

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Treenef don't do other people's homework. And second thats C++ in a C board.

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    18
    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

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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)

    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

  7. #7
    Registered User
    Join Date
    Apr 2005
    Posts
    18
    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");
    	
    }

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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;
    }

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    void perm(int n,int array[]){
    /* ... */
        printf("%d ", array);
    Opps.

  10. #10
    Registered User
    Join Date
    Apr 2005
    Posts
    18

    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???

  11. #11
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    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);
             }
    
    }

  12. #12
    Registered User
    Join Date
    Apr 2005
    Posts
    18
    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?

  13. #13
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Threads merged. In the future please keep to one thread for the same problem.

  14. #14
    Registered User
    Join Date
    Apr 2005
    Posts
    18
    ok sorry...so any suggestions?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  2. recursive permutations
    By wd_kendrick in forum C Programming
    Replies: 7
    Last Post: 06-02-2008, 03:11 PM
  3. permutations of a string
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-23-2006, 08:52 AM
  4. String permutations help
    By nickk in forum C Programming
    Replies: 4
    Last Post: 05-15-2004, 01:55 PM
  5. Permutations
    By kiddy in forum C++ Programming
    Replies: 1
    Last Post: 02-11-2002, 09:53 AM