Finding the index of a given permutation

Question

I'm reading the numbers 0, 1, ..., (N - 1) one by one in some order. My goal is to find the lexicography index of this given permutation, using only O(1) space.

This question was asked before, but all the algorithms I could find used O(N) space. I'm starting to think that it's not possible. But it would really help me a lot with reducing the number of allocations.

Answer 1

Considering the following data:

chars = [a, b, c, d]
perm = [c, d, a, b]
ids = get_indexes(perm, chars) = [2, 3, 0, 1]

A possible solution for permutation with repetitions goes as follows:

len = length(perm)         (len = 4)
num_chars = length(chars)  (len = 4)

base = num_chars ^ len     (base = 4 ^ 4 = 256)
base = base / len          (base = 256 / 4 = 64)

id = base * ids[0]         (id = 64 * 2 = 128)
base = base / len          (base = 64 / 4 = 16)

id = id + (base * ids[1])  (id = 128 + (16 * 3) = 176)
base = base / len          (base = 16 / 4 = 4)

id = id + (base * ids[2])  (id = 176 + (4 * 0) = 176)
base = base / len          (base = 4 / 4 = 1)

id = id + (base * ids[3])  (id = 176 + (1 * 1) = 177)

Reverse process:

id = 177
(id / (4 ^ 3)) % 4 = (177 / 64) % 4 =   2 % 4 = 2 -> chars[2] -> c
(id / (4 ^ 2)) % 4 = (177 / 16) % 4 =  11 % 4 = 3 -> chars[3] -> d
(id / (4 ^ 1)) % 4 = (177 / 4)  % 4 =  44 % 4 = 0 -> chars[0] -> a
(id / (4 ^ 0)) % 4 = (177 / 1)  % 4 = 177 % 4 = 1 -> chars[1] -> b

The number of possible permutations is given by num_chars ^ num_perm_digits, having num_chars as the number of possible characters, and num_perm_digits as the number of digits in a permutation.

This requires O(1) in space, considering the initial list as a constant cost; and it requires O(N) in time, considering N as the number of digits your permutation will have.

Based on the steps above, you can do:

function identify_permutation(perm, chars) {

    for (i = 0; i < length(perm); i++) {
        ids[i] = get_index(perm[i], chars);
    }

    len = length(perm);
    num_chars = length(chars);

    index = 0;
    base = num_chars ^ len - 1;
    base = base / len;
    for (i = 0; i < length(perm); i++) {
        index += base * ids[i];
        base = base / len;
    }

}

It's a pseudocode, but it's also quite easy to convert to any language (: