是否有一个函数 f(n) 返回有序组合列表中的第 n: 个组合而不重复？

当要选择的元素数 (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 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]

有谁知道这是否可行？

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

让我们首先对这个问题建立一些直觉。假设我们有n = 5（例如，集合{0, 1, 2, 3, 4}) and r = 3。这种情况下有多少种独特的组合？答案当然是5-choose-3，其评估结果为10。由于我们将按升序对组合进行排序，请考虑一下，一旦我们用尽了所有以0。这必须是4-choose-3, or 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))

I find,

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]

其中线性索引是从零开始的。