CodeDump : Permutations

CodeDump :: Categories :: PageIndex :: RecentChanges :: RecentlyCommented :: Login/Register

Generating the next permutation


up

Given a set of values with a lexicographical order, e.g. {a,b,c,d} where a<b, b<c, c<d. It's possible to generate some permutations e.g.
{d,c,a,b}, {c,a,b,d}. Now given a permutation, how does one generate the lexicographically next pernutation. This can be done by using the followin algorithm:

1) Find the largest position i such that a_{i} < a_{i+1}
2) Replace a_i with the smallest value a_{i+1}...a_{n} that is bigger than the value of a_{i}
3) Reassign the values from the remaining elements a_{i+1}...a_{n} (including the original a_{i}) 
in lexicographically increasing order.


Some prefer English, other prefer C:

#include <stdio.h>
#include <stdlib.h>

void print(int *buff)
{
    int i;
    for(i=0;i<10;i++)
    {
        printf("%d", buff[i]);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    int cur[10]={0,1,2,3,4,5,6,7,8,9};
    int tmp[10];
    int num=2;
    int i;

    // Reset the scratch buffer
    for(i=0;i<10;i++)
    {
        tmp[i]=0;
    }

    while(1)
    {

        // Find the largest position pos such that a_{pos} < a_{pos+1}
        int pos=8;
        while(cur[pos]>cur[pos+1])
        {
            pos--;
        }

        // Replace a_{pos} with the smallest value (maxVal) (a_{pos}...a_{n})
        // that is larger than a_{pos}
        int maxVal=cur[pos+1];
        i=pos+1;

        tmp[cur[pos]]=1;
        while(i != 10)
        {           
            tmp[cur[i]]=1;
            if(cur[i]>cur[pos] && cur[i]<maxVal)
            {
                maxVal=cur[i];
            }
            i++;
        }
        cur[pos++]=maxVal;
        tmp[maxVal]=0;

        // Reassign the values from the remaining elements into increasing order
        for(i=0;i<10;i++)
        {
            if(tmp[i]==1)
            {
                cur[pos++]=i;
                tmp[i]=0;
            }
        }

        // Print them
        printf("%d: ",num);
        print(cur);
        num++;
    }
    return 0;
}


This piece of code uses an array to store the current permutation, and while searching the next largest value the tmp array is filled the reamaining values. These can later be added to the next value by walking this array. So finding the next permutation using this algorithm is O(n) with n being the number of elements in the permutation.

up
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by Wikka Wakka Wiki 1.1.6.0
Page was generated in 0.1297 seconds