是否有一个函数 f(n) returns n:th 组合在有序组合列表中没有重复？
Is there a function f(n) that returns the n:th combination in an ordered list of combinations without repetition?
没有重复的组合看起来像这样，当可供选择的元素数量 (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循环的当前迭代值，如this jsfiddle example :
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 和 r 可用的所有组合集进行某种排序，这样线性索引才有意义。我建议我们同意让我们的组合保持递增顺序（或者至少是单个元素的索引），如您的示例所示。那么我们如何从线性索引到组合？
让我们首先对问题建立一些直觉。假设我们有 n = 5（例如集合 {0, 1, 2, 3, 4}）和 r = 3。在这种情况下有多少种独特的组合？答案当然是 5-choose-3，计算结果为 10。由于我们将按递增顺序对组合进行排序，因此请考虑一下，一旦我们用完所有以 0 开头的组合，还剩下多少组合。这必须是 4-choose-3，或总共 4。在这种情况下，如果我们最初要在索引 7 处寻找组合，这意味着我们必须减去 10 - 4 = 6 并在集合 [=26= 中搜索索引 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)
Test-driving 这是您的初始输入，
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]
其中线性索引为zero-based.
从结果的第一个元素开始。该元素的值取决于您可以使用较小元素获得的组合数。对于每个这样较小的第一个元素，第一个元素 k 的组合数是 n − k − 1 选择 r − 1，可能有一些 of-by-one 更正。所以你会对一堆二项式系数求和。 Wolfram Alpha can help you 计算这样的和，但结果中仍然有一个二项式系数。解决最大的 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。在那种情况下，我发现更容易考虑从列表的 end 中对项目进行编号。在 n = 5 和 r = 3 的情况下，您会得到 choose(2, 2)=1 以 2 开头的组合，以 choose(3,2)=3 开头的组合1 和 choose(4,2)=6 组合从 0 开始。所以在一般的 choose(n,r) 二项式系数中，每一步增加 n，并保持 r。考虑到 sum(choose(k,r) for k in range(r,n+1)) can be simplified 到 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，您也知道具有相同第一个元素的第一个组合的索引（也是从我上面的函数返回的）。您可以使用第一个索引和实际索引之间的差异作为递归调用的输入。递归调用将针对 r − 1 个选自 n − k − 1 的元素。而你将 k + 1 添加到递归调用的每个元素，因为顶层 returns 值从 0 开始，而下一个元素必须大于 k 为了避免重复。
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)])
我有一个 complete working example，包括 choose 的实现，更详细的文档字符串和一些基本假设的测试。
没有重复的组合看起来像这样，当可供选择的元素数量 (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循环的当前迭代值，如this jsfiddle example : 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 和 r 可用的所有组合集进行某种排序，这样线性索引才有意义。我建议我们同意让我们的组合保持递增顺序（或者至少是单个元素的索引），如您的示例所示。那么我们如何从线性索引到组合？
让我们首先对问题建立一些直觉。假设我们有 n = 5（例如集合 {0, 1, 2, 3, 4}）和 r = 3。在这种情况下有多少种独特的组合？答案当然是 5-choose-3，计算结果为 10。由于我们将按递增顺序对组合进行排序，因此请考虑一下，一旦我们用完所有以 0 开头的组合，还剩下多少组合。这必须是 4-choose-3，或总共 4。在这种情况下，如果我们最初要在索引 7 处寻找组合，这意味着我们必须减去 10 - 4 = 6 并在集合 [=26= 中搜索索引 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)
Test-driving 这是您的初始输入，
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]
其中线性索引为zero-based.
从结果的第一个元素开始。该元素的值取决于您可以使用较小元素获得的组合数。对于每个这样较小的第一个元素，第一个元素 k 的组合数是 n − k − 1 选择 r − 1，可能有一些 of-by-one 更正。所以你会对一堆二项式系数求和。 Wolfram Alpha can help you 计算这样的和，但结果中仍然有一个二项式系数。解决最大的 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。在那种情况下，我发现更容易考虑从列表的 end 中对项目进行编号。在 n = 5 和 r = 3 的情况下，您会得到 choose(2, 2)=1 以 2 开头的组合，以 choose(3,2)=3 开头的组合1 和 choose(4,2)=6 组合从 0 开始。所以在一般的 choose(n,r) 二项式系数中，每一步增加 n，并保持 r。考虑到 sum(choose(k,r) for k in range(r,n+1)) can be simplified 到 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，您也知道具有相同第一个元素的第一个组合的索引（也是从我上面的函数返回的）。您可以使用第一个索引和实际索引之间的差异作为递归调用的输入。递归调用将针对 r − 1 个选自 n − k − 1 的元素。而你将 k + 1 添加到递归调用的每个元素，因为顶层 returns 值从 0 开始，而下一个元素必须大于 k 为了避免重复。
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)])
我有一个 complete working example，包括 choose 的实现，更详细的文档字符串和一些基本假设的测试。