#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0

    How to create a int recursive permutation.


    Hey, i need help to finish a problem i have been trying to do for the past couple of days,

    what i need to do is create a recursive premutation with this header "int nextPermutation(int array[], int arraySize)"

    An example of what it does it this "Below is the sequence of permutations for n = 3, produced by applying
    nextPermutation consecutively:
    (1 2 3) ; (1 3 2) ; (3 1 2) ; (2 1 3) ; (2 3 1) ; (3 2 1)
    So, the nextPermutation applied to (1 , 2, 3) produces (1, 3, 2),
    applied to (1 , 3, 2) it produces (3, 1, 2),
    applied to (3, 1, 2) it produces (2, 1, 3)"


    So the logic of it is

    "If a1,...,an is an arbitrary permutation (where a1,...,an are the numbers 1, 2, …, n in a probably different order) then the “next” permutation is produced by the
    following procedure:
    (i) If the maximal element of the array (which is n) is not the first element of the
    array, say n=ai , where i>1 , then to produce the "next" permutation you need to swap ai and ai−1 .
    (ii) If the maximal element of the array is in the first position, i.e. n=a1 , then to
    produce the “next” permutation to the permutation (a1,...,an), first find the “next” permutation to the (n-1)-element permutation (a2,...,an), and then
    append a1 to the end of thus obtained array of (n-1) elements.


    I have attempted multiple different ways but i dont have a clue.

    For example i currently have ::
    (this doesn't work, just keep repeating the same thing over and over)
    Code:
    void swap(int A, int B){
        int temp;
        temp = A;
        A = B;
        B = temp;
    }
    
    
    int nextPermutation(int array[], int arraySize){
       int j;
       if (arraySize == 10)
         printf("%d\n", array);
       else
       {
            for (j = arraySize; j <= 10; j++)
           {
              swap(array[j], array[arraySize]);
              nextPermutation(array, arraySize+1);
              swap(array[j], array[arraySize]); //backtrack
           }
       }
    }
    
    
    int main(){
    
        int intArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        //int intArray[10] = {1, 10, 3, 9, 8, 6, 7, 2, 4, 5};
        nextPermutation(intArray, 0);
        int i = 0;
        for(i = 0; i < 10; i++){
            printf("%d ",intArray[i]);
        }

    i used to have something like this....
    (This is a snippet before i fixed the swap function and the swap call)
    Code:
    swap(int A, int B){
        int temp;
        temp = A;
        A = B;
        B = temp;
    }
    
    
    int max_array(int array[], int arraySize)
    {
       int i, max=-32000;
       for (i=0; i<arraySize; i++)
       {
         if (array[i]>max)
         {
            max=array[i];
         }
       }
       printf("%d \n Max array: ", max)
       return(max);
    }
    
    int nextPermutation(int array[], int arraySize){
        int i;
        n = max_array(array, arraySize);
        if (int i; n == array[i] && i > 1; i++){
            swap(array[i], array[i-1]);
        }
    
        else if(int i; n == array[i]; i++){
    
    
        }
    }
    
    void main(){
    
        int intArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        //int intArray[10] = {1, 10, 3, 9, 8, 6, 7, 2, 4, 5};
        nextPermutation(intArray, 10);
        int i = 0;
        for(i = 0; i < 10; i++){
            printf("%d ",intArray[i]);
        }

    But i keep getting confused and keep changing it because i think its all wrong with that its telling me to do..... Really got a massive headache over this.



    Also here is a further description if you guys need it
    "The function receives an integer array argument which is a permutation of integers 1, 2,
    …, n. If there is the “next permutation” (the meaning is described in the algorithm below)
    to the permutation represented by the array, then the function returns 1 (true) and the array
    is changed so that it represents the “next” permutation. If there is no “next” permutation,
    the function returns 0 (false) and does not change the array.

    Now, to list all the permutations of the numbers 1, 2, …, n, you start with the permutation
    (1, 2, …, n) and apply the above algorithm (function nextPermutation) to it to produce
    the "next" permutation. Then again you apply nextPermutation algorithm to thus produced
    permutation to obtain the "next" permutation etc. Proceeding in this way will allow you to
    produce all possible n! permutations of the numbers 1, 2, …, n (if you prove this fact
    rigorously, by mathematical induction, you will be awarded 2 bonus marks).
    Please note that the last permutation produced in this sequence is (n, …, 2, 1). And this is
    the only permutation that does not have the "next" permutation to it. "
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,894
    Rep Power
    481
    swap needs to work with pointers.

    Didn't bother to look at the rest of your algorithm.

    Comments on this post

    • jwdonahue agrees : Swap is definitely broken.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    In the first block of code, nextPermutation() violates seperation of concerns and the one responsibility rules. It prints data and implements an algorithm. Try not to mix those. Functions should do one thing and one thing only. Maybe that one thing is "print a bunch of data", but it should never be "print a bunch data AND do this other thing that has nothing do do with printing". So your original code (the second code block) is actually superior in this regard. Go back to it and fix swap(). Then we'll see whether you have other issues in there.
    I no longer wish to be associated with this site.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0
    Alright so now i have this:
    (Hope the swap is fixed :D)

    Code:
    void swap(int* A, int* B){
        int temp;
        temp = *A;
        *A = *B;
        *B = temp;
    }
    
    
    int max_array(int array[], int arraySize)
    {
       int i, max=-32000;
       for (i=0; i<arraySize; i++)
       {
    	 if (array[i]>max)
    	 {
    	    max=array[i];
    
    	 }
       }
       printf("%d \n Max array: ", i);
       return(i);
    }
    
    int nextPermutation(int array[], int arraySize){
        int i;
        int max = 10;
        int n = max_array(array, arraySize);
        if (arraySize == max-1){
                 for(i=0;i<n;i++)
                   {
                          printf("%d",array[i]);
                   }
                   printf("\n");
        }
    
        for(i=0;i<max;i++)
                {
                   if(array[i]==0)
                   {
                       swap(&array[i], &array[arraySize]);
                       nextPermutation(array, arraySize+1);
                       swap(&array[i], &array[arraySize]);
                   }
                }
    
    
    
        }
    
    
    int main(){
    
        int intArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        //int intArray[10] = {1, 10, 3, 9, 8, 6, 7, 2, 4, 5};
        nextPermutation(intArray, 0);
        int i = 0;
        for(i = 0; i < 10; i++){
            printf("%d ",intArray[i]);
        }
    
    
    }

    Someone has suggested to this as some help ::

    Code:
    int ct=-1,n=10,temp[10]={0,0,0,0,0,0,0,0,0,0};
        int intArray[10]={1,2,3,4,5,6,7,8,9,10};
    
        permute(int k) 
        {     
                int i;     
                temp[k]=++ct;     
                if(ct==n-1)     
                {         
                   for(i=0;i<n;i++)         
                   {
                          printf("%d",intArray[temp[i]]);         
                   }
                   printf("\n");     
                }     
                for(i=0;i<n;i++)     
                {
                   if(temp[i]==0)     
                   {
                       permute(i);     
                   }
                }
                ct--;     
                temp[k]=0;       
        } 
    
        int main() 
        {     
          permute(0);     
        }
    But doesnt help too much since i require the Permute function to take 2 inputs and i think only use 1 array and such so i'm not exactly sure what to change.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Originally Posted by Chackonman
    Alright so now i have this:
    (Hope the swap is fixed :D)
    You hope it's fixed? What happens when you run the program?
    I no longer wish to be associated with this site.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2009
    Posts
    5
    Rep Power
    0
    Well from the current code I don't think it does nothing but can't check atm out of house.

    But yeah I noticed no real changes due to the full program being incomplete

IMN logo majestic logo threadwatch logo seochat tools logo