2012年9月23日 星期日

Permutation in C

the permutation in c

the process is:
First,
find the first l from left to right that p[l]<p[l+1]
Next,
find the first r from left to right again that p[l]<p[r]
so p[r] is the only one bigger than p[l]
then
swap p[l] and p[r]
and
reverse p[l+1...n-1]
code:
//iteration called:perm(p[],n)
void perm(char *p,int n)
{
    char t;
    int l,r;
    while(1){
        printf("%s\n",p);
        for(l=n-2;l>=0&&p[l]>p[l+1];l--);
        if(l<0)break;
        for(r=n-1;p[l]>p[r];r--);
        SWAP(p[l],p[r],t);
        for(++l,r=n-1;l<r;l++,r--)
            SWAP(p[l],p[r],t);
    }
}
//recursion called:perm2(p[],a[],output[],n,0)
//a[] is to reflect with p[] that can decide
//      which item should be put in o[]
void perm2(char *p,char *o,int *a,int n,int count)
{
    if(count==n){
        printf("%s\n",o);
        count--;
        return ;
    }
    int i;
    for(i=0;i<n;i++){
        if(a[i])continue;
        a[i] = 1;
        o[count++] = p[i];
        perm2(p,o,a,n,count);
        a[i] = 0;
        count--;
    }
}

沒有留言:

張貼留言