找到一个给定的排列的索引 [英] Finding the index of a given permutation

问题描述

我读了数 0，1，...，（N - 1）逐个一些订单。我的目标是要找到这个特定置换的词典编纂指标，只用 O（1）的空间。

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.

这个问题被问过，但所有的算法我能找到使用 O（N）的空间。我开始认为这是不可能的。但是，这将真正帮助我很多以减少分配的数量。

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.

推荐答案

考虑以下数据：

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

可能的排列数量由 NUM_CHARS给出^ num_perm_digits ，有 NUM_CHARS 作为可能的字符数，和 num_perm_digits 为一个数字的排列数。

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.

这需要 O（1）空间，考虑到初始列表作为一个恒定的费用;它要求 O（N）的时候，考虑到 N 为一个数字的排列将有多少。

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;
    for (i = 0; i < length(perm); i++) {
        index += base * ids[i];
        base = base / len;
    }

}

这是一个伪code，但它也很容易转换成任何语言（：

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

这篇关于找到一个给定的排列的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！