math - 是否有函数 f(n) 返回 n :th combination in an ordered list of combinations without repetition?

Question

没有重复的组合看起来像这样，当可供选择的元素数 (n) 为 5 且选择的元素数 (r) 为 3 时:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

随着 n 和 r 的增长，组合的数量会很快变大。对于 (n,r) = (200,4)，组合数为 64684950。

很容易用 r 个嵌套的 for 循环迭代列表，其中每个 for 循环的初始迭代值大于嵌套它的 for 循环的当前迭代值，如以下 jsfiddle 示例所示: https://dotnetfiddle.net/wHWK5o

我想要的是一个根据其索引仅计算一个组合的函数。像这样:

tuple combination(i,n,r) {
  return [combination with index i, when the number of elements to choose from is n and elements chosen is r]

有人知道这是否可行吗？

Answer 1

您首先需要对给定 n 和 r 可用的所有组合集合进行某种排序，这样线性索引才有意义。我建议我们同意让我们的组合保持递增顺序(或者至少是单个元素的索引)，如您的示例所示。那么我们如何才能从线性索引变为组合索引呢？

让我们首先为这个问题建立一些直觉。假设我们有 n = 5(例如集合 {0, 1, 2, 3, 4})和 r = 3。在这种情况下有多少种独特的组合？答案当然是 5-choose-3，其计算结果为 10。由于我们将按递增顺序对组合进行排序，因此请考虑一下，一旦我们用完所有以 0 开头的组合，还剩下多少组合。这必须是 4-choose-3，或者总共是 4。在这种情况下，如果我们最初在索引 7 处寻找组合，这意味着我们必须减去 10 - 4 = 6 并在索引 处搜索组合>1 在集合 {1, 2, 3, 4} 中。这个过程一直持续到我们找到一个小于这个偏移量的新索引。

一旦这个过程结束，我们就知道了第一个数字。那么我们只需要确定剩余的r - 1位即可!算法因此形成如下(在 Python 中，但这应该不会太难翻译)，

from math import factorial


def choose(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))


def combination_at_idx(idx, elems, r):
    if len(elems) == r:
        # We are looking for r elements in a list of size r - thus, we need
        # each element.
        return elems

    if len(elems) == 0 or len(elems) < r:
        return []

    combinations = choose(len(elems), r)    # total number of combinations
    remains = choose(len(elems) - 1, r)     # combinations after selection

    offset = combinations - remains

    if idx >= offset:       # combination does not start with first element
        return combination_at_idx(idx - offset, elems[1:], r)

    # We now know the first element of the combination, but *not* yet the next
    # r - 1 elements. These need to be computed as well, again recursively.
    return [elems[0]] + combination_at_idx(idx, elems[1:], r - 1)

根据您的初始输入进行测试，

N = 5
R = 3

for idx in range(choose(N, R)):
    print(idx, combination_at_idx(idx, list(range(N)), R))

我发现，

0 [0, 1, 2]
1 [0, 1, 3]
2 [0, 1, 4]
3 [0, 2, 3]
4 [0, 2, 4]
5 [0, 3, 4]
6 [1, 2, 3]
7 [1, 2, 4]
8 [1, 3, 4]
9 [2, 3, 4]

其中线性索引从零开始。