permutation.cc

// Index <-> Permutation

// Compile: g++ -Wall -o p permutation.cc

#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define N       5
#define NFACT   120

void
index_to_permutation(uint32_t n, int permutation[N]) {
    uint32_t nf = NFACT;
    for (int i = 0; i < N; ++i) {
        nf /= N - i;
        permutation[i] = n / nf;
        n %= nf;
    }

    // convert from index-in-remainining-items to permutation
    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (permutation[j] >= permutation[i])
                permutation[j] += 1;
        }
    }
}

uint32_t
permutation_to_index(const int orig_permutation[N]) {
    uint32_t permutation[N];
    memcpy(permutation, orig_permutation, N * sizeof(permutation[0]));

    // convert from permutation to index-in-remainining-items
    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (permutation[j] > permutation[i])
                permutation[j] -= 1;
        }
    }

    uint32_t index = 0;
    uint32_t nf = 1;
    for (int i = 1; i < N; ++i) {
        index += nf * permutation[N - i];
        nf *= i;
    }

    return index;
}

int
main(void) {
    int p[N];
    for (int i = 0; i < 10; ++i) {
        // convert from index i to permutation p
        index_to_permutation(i, p);
        // convert permutation p back to index j -> check if i == j
        uint32_t j = permutation_to_index(p);

        // dump i, p, j
        printf("p(%d) = ", i);
        for (int k = 0; k < N; ++k)
            printf("%c%d", (k == 0) ? '[': ',', p[k]);
        printf("] = p(%d)\n", j);
    }
    return 0;
}

// vim: set sw=4 ts=4 et: