有没有一个函数 f(n) 可以返回在无重复组合按顺序排列的列表中第 n 个组合？

Question

有没有一个函数 f(n) 可以返回在无重复组合按顺序排列的列表中第 n 个组合？

4

当要选择的元素数量（n）为5，选中的元素数量（r）为3时，没有重复的组合看起来像这样：

随着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]

有人知道这是否可行吗？

- Martin

谢谢，拼写错误。 - Martin

2个回答

1

从结果的第一个元素开始。该元素的值取决于您可以使用较小元素获得的组合数。对于每个这样的较小第一个元素，第一个元素为k的组合数为n−k−1选择r−1，可能需要一些加一或减一的修正。因此，您需要对许多二项式系数求和。Wolfram Alpha 可以帮助您计算这样的总和，但结果仍然包含一个二项式系数。解出最大的k，使得总和不超过给定的索引i是一项计算，您不能使用简单的方法（例如平方根）来完成。您需要循环测试可能的值，例如像这样：

def first_naive(i, n, r):
  """Find first element and index of first combination with that first element.

  Returns a tuple of value and index.

  Example: first_naive(8, 5, 3) returns (1, 6) because the combination with
  index 8 is [1, 3, 4] so it starts with 1, and because the first combination
  that starts with 1 is [1, 2, 3] which has index 6.
  """
  s1 = 0
  for k in range(n):
    s2 = s1 + choose(n - k - 1, r - 1)
    if i < s2:
      return k, s1
    s1 = s2

您可以使用二分法将O（n）循环迭代减少到O（log n）步，这对于大的n尤其相关。在这种情况下，我发现从列表的末尾开始编号更容易理解。在n = 5和r = 3的情况下，您得到以2开头的choose(2,2)=1组合，以1开头的choose(3,2)=3组合和以0开头的choose(4,2)=6组合。因此，在一般的choose(n,r)二项式系数中，您会随着每一步增加n并保持r不变。考虑到sum(choose(k,r) for k in range(r,n+1))可以简化为choose(n+1,r+1)，您最终可以提出以下二分条件：

def first_bisect(i, n, r):
  nCr = choose(n, r)
  k1 = r - 1
  s1 = nCr
  k2 = n
  s2 = 0
  while k2 - k1 > 1:
    k3 = (k1 + k2) // 2
    s3 = nCr - choose(k3, r)
    if s3 <= i:
      k2, s2 = k3, s3
    else:
      k1, s1 = k3, s3
  return n - k2, s2

一旦你知道第一个元素是k，你也知道具有相同第一个元素的第一个组合的索引（也从我的上面的函数返回）。您可以使用该第一个索引与实际索引之间的差作为递归调用的输入。递归调用将选择从n - k - 1中选择r - 1个元素。由于顶层返回从0开始的值，而下一个元素必须大于k才能避免重复，因此您需要将k + 1添加到递归调用中的每个元素。

def combination(i, n, r):
  """Compute combination with a given index.

  Equivalent to list(itertools.combinations(range(n), r))[i].

  Each combination is represented as a tuple of ascending elements, and
  combinations are ordered lexicograplically.

  Args:
    i: zero-based index of the combination
    n: number of possible values, will be taken from range(n)
    r: number of elements in result list
  """
  if r == 0:
    return []
  k, ik = first_bisect(i, n, r)
  return tuple([k] + [j + k + 1 for j in combination(i - ik, n - k - 1, r - 1)])

我有一个完整的工作示例，包括choose的实现、更详细的文档字符串和对一些基本假设的测试。

- MvG

谢谢，这是减少到达给定组合索引所需迭代次数的好方法，但由于建议本质上与N. Wouda的答案相同，并且该答案比您的答案更早，因此我将标记该答案为被接受的解决方案。 - Martin

@Martin：当然，如果你不需要二分法，N. Wouda的答案完全值得被接受。我现在已经增加了一些代码片段来帮助未来的读者，特别是因为二分法方法留下了足够的空间，容易出现差一或错误符号的错误，所以我尝试了几次才弄对了。 - MvG

好的，那么这是一种非常快速的解决方案，适用于几乎任何n和r。我将把它标记为被接受的答案，因为这是任何遇到此问题的人都在寻找的答案。向你致敬。 - Martin

有没有办法将其扩展以切片组合？即返回索引i和索引j之间的所有组合list(itertools.combinations())[i:j]。 - Gaberocksall

@Gaberocksall：一旦你得到了上面算法的第一个组合，获取下一个组合就相当简单了。尝试增加最后一个元素。如果它达到了 n，则将其前面的位置加1，然后使最后一个位置比那个更大。如果倒数第二个元素达到了 n-1，则增加它之前的位置。继续向左移动增量位置，直到找到可以增加的位置为止。如果这不够清楚，最好在另一个问题中讨论。我希望这样的问题已经存在，但现在没有时间去查看。 - MvG

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nelewout · Accepted Answer

您需要首先对给定的n和r的所有组合进行某种排序，以便线性索引有意义。我建议我们同意按升序保留组合（或者至少单个元素的索引），就像您的示例一样。那么我们如何从线性索引转换为组合呢？

让我们先为这个问题建立一些直觉。假设我们有n = 5（例如集合{0,1,2,3,4}）和r = 3。在这种情况下有多少个唯一的组合？答案当然是5选择3，计算结果为10。由于我们将按升序排列我们的组合，请花一分钟考虑一下一旦我们用0开头的组合耗尽后还剩下多少组合。这必须是4选择3，或总共4个。在这种情况下，如果我们最初正在寻找索引7处的组合，则意味着我们必须减去10-4 = 6，并在集合{1,2,3,4}中搜索索引1处的组合。此过程继续，直到找到比该偏移量更小的新索引为止。

一旦此过程结束，我们就知道第一个数字。然后我们只需要确定剩余的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]

线性索引从零开始计数。