/*
perm.c 順列に対応する整数への変換とその逆変換の簡略版
   programmed by Isaku WADA 2009 isaku@pb4.so-net.ne.jp
 */
#include <stdio.h>

#define MAX_N 50
#define MAX_R 50

int n,r;
unsigned a[MAX_R][MAX_N];

unsigned InitPerm(int nn,int rr) {
    int i,j;
    n=nn; r=rr;
    if (r<=0||n<=0||r>n||r>MAX_R||n>MAX_N) return 0;
    for (i=r-1;i>=0;i--) {
        if (i==r-1) a[i][0]=1; else a[i][0]=a[i+1][n-i-2];
        for (j=1;j<n-i;j++) a[i][j]=a[i][0]+a[i][j-1];
    }
    for (i=0;i<r;i++) for (j=1;j<n-i;j++) if (a[i][j]<=a[i][j-1])
        return 0;
    return a[0][n-1];
}

unsigned PermToNum(int*vec) {
    int i,j,k; unsigned u=0;
    for (i=0;i<r;i++) {
        for (k=vec[i],j=0;j<i;j++) if (vec[j]<vec[i]) k--;
        if (k) u+=a[i][k-1];
    }
    return u;
}

void NumToPerm(int*vec,unsigned num) {
    int i,j,k; char f[MAX_N];
    for (j=0;j<n;j++) f[j]=0;
    for (i=0;i<r;i++) {
        for (k=0;a[i][k]<=num;k++) ;
        if (k) num-=a[i][k-1];
        for (j=0;k>=0;k--,j++) while (f[j]) j++;
        f[--j]=1; vec[i]=j;
    }
}

int main(void)
{
    unsigned i,s;  int vec[2];

    s=InitPerm(4,2);
    for (i=0;i<s;i++) {
        printf(" %2u -> ", i);
        NumToPerm(vec,i);
        printf("(%d,%d)",vec[0],vec[1]);
        printf(" -> %2u\n", PermToNum(vec));
    }
    return 0;
}