数组中组合索引的算法

Question

我知道如何计算 binomial coefficient 给定的 n 和 k（我为此使用了一个库）。现在假设您将所有这些组合存储在一个数组中。每个组合都有一个索引。我实际上不需要将它们存储在数组中，但我需要知道，如果我要存储它们，每个组合的数组索引是什么。

例如给定 C(n,k) 一组可能组合的一个元素，我需要一个函数来为我提供它在数组中的索引 i，而无需实际创建整个数组。编程语言无所谓，虽然我需要在 java 中实现该功能，但是任何（伪）语言算法都可以，然后我将其翻译为 java.

比如在n=5和k=2的情况下，我凭经验定义这个函数f(n, k, [a,b]) => N为：

f(5, 2, [1,2]) = 0
f(5, 2, [1,3]) = 1
f(5, 2, [1,4]) = 2
f(5, 2, [1,5]) = 3
f(5, 2, [2,3]) = 4
f(5, 2, [2,4]) = 5
f(5, 2, [2,5]) = 6
f(5, 2, [3,4]) = 7
f(5, 2, [3,5]) = 8
f(5, 2, [4,5]) = 9

表示 (3,5) 组合将占用数组中的索引 8。 n=5 和 k=3 的另一个例子是 f(n, k, [a,b,c]) => N，根据经验定义为

f(5, 3, [1,2,3]) = 0
f(5, 3, [1,2,4]) = 1
f(5, 3, [1,2,5]) = 2
f(5, 3, [1,3,4]) = 3
f(5, 3, [1,3,5]) = 4
f(5, 3, [1,4,5]) = 5
f(5, 3, [2,3,4]) = 6
f(5, 3, [2,3,5]) = 7
f(5, 3, [2,4,5]) = 8
f(5, 3, [3,4,5]) = 9

编辑以在评论后澄清：

在上面的例子中，[1,2,3], [2,4,5]等等，都是C(n,k)集合中的一个元素，例如n 个可能数字中 k 个数字的可能组合之一。该函数需要它们来计算它们在数组中的索引。

但是我需要为 n 和 k 的泛型值编写此函数，而无需创建数组。也许这样的函数已经存在于某些组合微积分库中，但我什至不知道如何调用它。

Answer 1

您应该看看 combinatorial number system，尤其是 "Place of a combination in the ordering" 部分。

甚至还有一个可能对您有所帮助的示例：National Lottery example in Excel。（抱歉，我不能在这里输入任何数学。）

在你的情况下，这将是

f(5, 3, [2,3,4]) = binom(5,3) - 1 - binom(5-2,3) - binom(5-3,2) - binom(5-4,1) =
                 = 10 - 1 - 1 - 1 - 1 = 6

或者如果您接受相反的订单，您可以省略 binom(5,3) - 1 部分并计算

f'(5, 3, [2,3,4]) = binom(5-2,3) + binom(5-3,2) + binom(5-4,1) - 1 =
                  = 1 + 1 + 1 - 1 = 2

（这应该可以为您节省一些时间，因为 binom(5, 3) 在这里并不是必需的。）

在Java中，方法可能是

int f(int n, int k, int[] vars) {
    int res = binom(n, k) - 1;

    for(int i = 0; i < k; i++) {
        res -= binom(n - vars[i], k - i);
    }

    return res;
}

或

int fPrime(int n, int k, int[] vars) {
    int res = -1;

    for(int i = 0; i < k; i++) {
        res += binom(n - vars[i], k - i);
    }

    return res;
}

假设方法 int binom(int n, int k) 和 binom(n, k) = 0 用于 n < k。

数组中组合索引的算法

Algorithm for combination index in array

algorithm

combinations