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

#define N 10

int n = N, i;
int data[N], available[N];

void gen_rand_perm(void) {
    srand((unsigned)time(NULL));  

    for (i = 0; i < n; i++)
        data[i] = i + 1;

    for (i = 0; i < n - 1; i++) {
        int tmp = data[i];
        int r = rand() % N;
        data[i] = data[r];
        data[r] = tmp;
    }

    for (i = 0; i < n; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

int fact(int i) {
    int result = 1, j;
    for (j = 2; j <= i; j++)
        result *= j;
    return result;
}

int rank() {
    // rank data into result
    int result = 0;
    for (i = 0; i < n - 1; i++) {
        result += data[i] * fact(n - i - 1);
    }
    return result;
}

void unrank(int number) {
    // unrank number into data
    // search for n such that n! <= number & (n + 1)! > number
    int k = 0;
    int j = 0;
    for (j = 0; j < n; j++)
        available[j] = 1;
    while (number > 0) {
        int j;
        for (j = n - 1; j >= 0; j--) {
            if (fact(j) <= number && fact(j + 1) > number) {
                data[k] = number / fact(j);
                available[data[k]] = 0;
                k++;
                number %= fact(j);
            }
        }
    }
    while (j < n) {
        if (available[j])
            data[k++] = j;
        j++;
    }
}

void gen_sol(int k) {
    if (k >= n) {
        for (i = 0; i < n; i++)
            printf("%d ", data[i] + 1);
        printf("\n");
        return;
    }

    int j;
    for (j = 0; j < n; j++) {
        if (available[j]) {
            data[k] = j;
            available[j] = 0;
            gen_sol(k + 1);
            available[j] = 1;
        }
    }
}

#define TEST_GEN_SOL

int main(void) {
#ifdef TEST_GEN_SOL
    freopen("permutari.in", "r", stdin);
    freopen("permutari.out", "w", stdout);

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        available[i] = 1;
    gen_sol(0);
    return 0;
#endif
    n = 3;
    data[0] = 1;
    data[1] = 0;
    data[2] = 2;
    int r;
    printf("rank = %d\n", (r = rank()));
    unrank(r);
    for (i=0;i<n;i++)
        printf("%d ", data[i]);
    printf("\n");
    return 0;
}