4

我有一个按字典顺序排列的集合 {1, 2, ... , n} 中所有大小为 k 的子集的列表，例如集合 {1, 2, 3, 4} 中大小为 2 的所有子集是 { 1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}。其中 {1, 2} 的索引为 0，{1, 3} 为 1，依此类推。

现在，我需要编写一个算法来接收一个子集（假设子集是有序的），并返回它在列表中的索引。

我写了以下算法：

int GetSubsetIndex(List<int> subset, int N)
{
    int Skip = 0;
    int Last = 0;
    int Depth = 1;
    int K = subset.Count;

    while (Depth <= K)
    {
        for (int i = Last + 1; i < subset[Depth - 1]; i++)
        {
            Skip += BinomialCoefficient(N - i, K - Depth);
        }

        Last = subset[Depth - 1];
        Depth++;
    }

    return Skip;
}

该算法使用子集字典顺序的特殊结构，解释如下：

假设我们有一组大小为 6（N=6）和长度为 3（K=3）的子集，那么我们有 6 个选择 3 个子集。现在，以 1 开头的子集数量为 5 选择 2，以 2 开头的子集数量为 4 选择 2，依此类推...

如果子集中的第一个数字是 X，我们可以跳过 (N-1 选择 K-1) + (N-2 选择 K-1) + ... + (NX 选择 K-1) 个子集。如果 X 是第一个数字，则子集中的第二个数字 Y 至少为 X+1。现在我们可以跳过 (N-[X+1] 选择 K-2) + (N-[X+2] 选择 K-2) + ... + (NY 选择 K-2) 等等。

在算法的代码中，Skip 表示我们跳过的子集的数量，last 表示我们在子集中考虑的最后一个数字（初始化为 0，因为集合以 1 开头），Depth 是我们在子集中的深度，K 是所有子集的长度。

这个算法的问题是，O(N)如果二项式系数计算是O(1)（如果它是预处理的）或O(N*k)（如果不是），那么它会随着时间的推移而运行，实际上一些子集可能会很快计算出来。我试图想办法在较短的时间内获得这个索引。

只要您不使用超过O(N chooke K)内存（即子集的数量），您就可以进行任何您想要的预处理。

4

1 回答 1

2

您想要的答案是组合数系统。见http://en.wikipedia.org/wiki/Combinatorial_number_system

您可以找到指令来查找大小为 k 的第 n 个子集，或者对于大小为 k 的子集，找到它的索引。

于 2014-02-18T23:51:29.857 回答