有没有直接获取nCr所有组合的有序集合中第N个组合的方法？
例如：我有四个元素：[6, 4, 2, 1]。取其中三个的所有可能组合为：[[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]]。
是否有一种算法能够让我直接获取有序结果集中第三个答案 [6, 2, 1]，而不必枚举所有之前的答案？
第N个组合
18
- Sami
5
1你如何定义“顺序”？假设你有序列（1、2、3、4、5、6、7、8、9）。在所有可能的四个组合中，第一个是什么？第二个呢？ - Bruno Reis
输入将是一个有序集合/数组，例如[n1，n2，n3，n4]。然后顺序将是数组中的索引。 - Sami
忽略我的上一个评论 :-) .. 针对组合之间的顺序，我要找的是这样一种顺序：一个含有元素n1的组合比一个不含元素n1的组合有更高的顺序...... 然后同样适用于n2等元素。 - Sami
因此，对于 nC3 组合，完整的顺序将会是：
[n1, n2, n3]、[n1, n2, n4]、[n1, n2, 1]、...、[n1, 2, 1]、[n2, n3, n4]、...、[3, 2, 1]。 - Sami
1让我们再试一次：
[
[i1，i2，i3]
[i1，i2，i4]
...
[i1，i2，in]
[i1，i3，i4]
...
...
[i1，i（n-1），in]
...
...
[i（n-2），i（n-1），in]
] - Sami
6个回答
17
请注意，您可以通过递归地生成带第一个元素的所有组合，然后生成不带第一个元素的所有组合来生成该序列。在两种递归情况下，您都需要删除第一个元素以获得从 n-1 个元素中获取的所有组合。在Python中：
def combination(l, r):
if r == 0:
yield []
elif len(l) == r:
yield l
else:
for c in (combination(l[1:], r-1)):
yield l[0:1]+c
for c in (combination(l[1:], r)):
yield c
如果您通过做出选择来生成序列，您可以通过计算一个选择生成多少个元素并将其与 k 进行比较，来递归地生成第 k 个元素。如果 k 小于该计数，则进行该选择。否则，减去该计数并在该点上重复其他可能的选择。如果总是有b种选择，您可以将其视为以基数b生成数字。即使选择的数量不同，这种技术仍然有效。在伪代码中（当所有选择始终可用时）：
kth(k, choicePoints)
if choicePoints is empty
return empty list
for each choice in head of choicePoints:
if k < size of choice
return choice and kth(k, tail of choicePoints)
else
k -= size of choice
signal exception: k is out-of-bounds
这将给您一个基于0的索引。如果您想要基于1，将比较改为 k <= 选择的大小。
难点（并且在伪代码中未指定）是选择的大小取决于先前的选择。请注意，伪代码可用于解决比问题更普遍的情况。
对于此特定问题，有两个选择 (b= 2)，第一个选择的大小（即包括第1个元素）由n-1Cr-1给出。以下是一个实现（需要适当的 nCr）：
def kthCombination(k, l, r):
if r == 0:
return []
elif len(l) == r:
return l
else:
i=nCr(len(l)-1, r-1)
if k < i:
return l[0:1] + kthCombination(k, l[1:], r-1)
else:
return kthCombination(k-i, l[1:], r)
如果你颠倒选项的顺序，就会颠倒序列的顺序。
def reverseKthCombination(k, l, r):
if r == 0:
return []
elif len(l) == r:
return l
else:
i=nCr(len(l)-1, r)
if k < i:
return reverseKthCombination(k, l[1:], r)
else:
return l[0:1] + reverseKthCombination(k-i, l[1:], r-1)
应用：
>>> l = [6, 4, 2, 1]
>>> [kthCombination(k, [6, 4, 2, 1], 3) for k in range(nCr(len(l), 3)) ]
[[6, 4, 2], [6, 4, 1], [6, 2, 1], [4, 2, 1]]
>>> powOf2s=[2**i for i in range(4,-1,-1)]
>>> [sum(kthCombination(k, powOf2s, 3)) for k in range(nCr(len(powOf2s), 3))]
[28, 26, 25, 22, 21, 19, 14, 13, 11, 7]
>>> [sum(reverseKthCombination(k, powOf2s, 3)) for k in range(nCr(len(powOf2s), 3))]
[7, 11, 13, 14, 19, 21, 22, 25, 26, 28]
- outis
15
- TLDR? 如果你只是想快速看到最终结果，可以直接滚动到底部查看我的最终解决方案。
我在寻找一种方法来获取一个指定组合在词典排序的列表中的索引位置，并且反过来，对于从一些可能非常巨大的对象集合中选择的对象，我找不到后者的相关资料。
既然我也曾经解决了（我认为是）与您完全相同的问题，所以我打算在这里发布我的两个解决方案。
**
编辑：我的需求正是您的要求 - 我看到答案并认为递归很好。 现在，经过长达六年的努力，您已经拥有它； 只需向下滚动即可。
**
对于我认为在问题中提出的您的要求，这将非常好地完成工作：
def iterCombinations(n, k):
if k==1:
for i in range(n):
yield [i]
return
result = []
for a in range(k-1, n):
for e in iterCombinations(n, k-1):
if e[-1] == a:
break
yield e + [a]
你可以在按降序排列的集合中查找该项（或使用某种等效的比较方法），因此对于所讨论的情况：
>>> itemsDescending = [6,4,2,1]
>>> for c in iterCombinations(4, 3):
... [itemsDescending[i] for i in c]
...
[6, 4, 2]
[6, 4, 1]
[6, 2, 1]
[4, 2, 1]
在 Python 中，这也是直接开箱即用的。
>>> import itertools
>>> for c in itertools.combinations(itemsDescending, 3):
... c
...
(6, 4, 2)
(6, 4, 1)
(6, 2, 1)
(4, 2, 1)
以下是我针对我的需求（实际上也是你的需求！）做出的一个非递归算法，该算法不会为任何方向创建或遍历有序列表，而是使用一种简单但有效的非递归nCr （即组合数）的实现方法：
def choose(n, k):
'''Returns the number of ways to choose k items from n items'''
reflect = n - k
if k > reflect:
if k > n:
return 0
k = reflect
if k == 0:
return 1
for nMinusIPlus1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)):
n = n * nMinusIPlus1 // i
return n
要在正向排序的列表中获取某个（从零开始的）索引处的组合：
def iterCombination(index, n, k):
'''Yields the items of the single combination that would be at the provided
(0-based) index in a lexicographically sorted list of combinations of choices
of k items from n items [0,n), given the combinations were sorted in
descending order. Yields in descending order.
'''
if index < 0 or index >= choose(n, k):
return
n -= 1
for i in range(k):
while choose(n, k) > index:
n -= 1
yield n
index -= choose(n, k)
n -= 1
k -= 1
要获取某个组合在倒序列表中所对应的（从零开始的）索引：
def indexOfCombination(combination):
'''Returns the (0-based) index the given combination would have if it were in
a reverse-lexicographically sorted list of combinations of choices of
len(combination) items from any possible number of items (given the
combination's length and maximum value)
- combination must already be in descending order,
and it's items drawn from the set [0,n).
'''
result = 0
for i, a in enumerate(combination):
result += choose(a, i + 1)
return result
对于你的示例来说，这有些过度了（但我现在意识到那只是一个例子）; 这是每个索引项的处理方式：
def exampleUseCase(itemsDescending=[6,4,2,1], k=3):
n = len(itemsDescending)
print("index -> combination -> and back again:")
for i in range(choose(n, k)):
c = [itemsDescending[j] for j in iterCombination(i, n, k)][-1::-1]
index = indexOfCombination([itemsDescending.index(v) for v in c])
print("{0} -> {1} -> {2}".format(i, c, index))
>>> exampleUseCase()
index -> combination -> and back again:
0 -> [6, 4, 2] -> 0
1 -> [6, 4, 1] -> 1
2 -> [6, 2, 1] -> 2
3 -> [4, 2, 1] -> 3
这个函数可以在眨眼间找到一个长列表中的索引或返回某个天文数字索引处的组合，例如：
>>> choose(2016, 37)
9617597205504126094112265433349923026485628526002095715212972063686138242753600
>>> list(iterCombination(_-1, 2016, 37))
[2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003,
2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989,
1988, 1987, 1986, 1985, 1984, 1983, 1982, 1981, 1980, 1979]
或者，因为那是最后一个，由于在选择（n，k）中的反射作用，它可能会很快，这里有一个来自中间位置的，看起来同样快...
>>> choose(2016, 37)//2
4808798602752063047056132716674961513242814263001047857606486031843069121376800
>>> list(iterCombination(_, 2016, 37))
[1978, 1973, 1921, 1908, 1825, 1775, 1747, 1635, 1613, 1598, 1529, 1528, 1521,
1445, 1393, 1251, 1247, 1229, 1204, 1198, 922, 901, 794, 699, 685, 633, 619, 598,
469, 456, 374, 368, 357, 219, 149, 93, 71]
这个最后的例子稍微让人思考了一下，但你也会这么做吧？
>>> import random
>>> rSet = set(random.randint(0, 10000000) for i in range(900))
>>> len(rSet)
900
>>> rList = sorted(rSet, reverse=True)
>>> combinations.indexOfCombination(rList)
61536587905102303838316048492163850175478325236595592744487336325506086930974887
88085020093159925576117511028315621934208381981476407812702689774826510322023536
58905845549371069786639595263444239118366962232872361362581506476113967993096033
00541202874946853699568596881200225925266331936183173583581021914595163799417151
30442624813775945054888304722079206982972852037480516813527237183254850056012217
59834465303543702263588008387352235149083914737690225710105023486226582087736870
38383323140972279867697434315252036074490127510158752080225274972225311906715033
86851377357968649982293794242170046400174118714525559851836064661141086690326842
25236658978135989907667078625869419802333512020715700514133380517628637151215549
05922388534567108671308819960483147825031620798631811671493891643972220604919591
22785587505280326638477135315176731640100473359830821781905546117103137944239120
34912084544221250309244925308316352643060056100719194985568284049903555621750881
39419639825279398618630525081169688672242833238889454445237928356800414839702024
66807635358129606994342005075585962080795273287472139515994244684088406544976674
84183671032002497594936116837768233617073949894918741875863985858049825755901232
89317507965160689287607868119414903299382093412911433254998227245783454244894604
83654290108678890682359278892580855226717964180806265176337132759167920384512456
91624558534942279041452960272707049107641475225516294235268581475735143470692000
78400891862852130481822509803019636619427631175355448729708451565341764545325720
79277290914349746541071731127111532099038538549697091038496002102703737347343739
96398832832674081286904287066696046621691978697914823322322650123025472624927566
99891468668052668317066769517155581261265629289158798073055495539590686279250097
27295943276536772955923599217742543093669565147228386873469711200278811335649924
13587219640724942441913695193417732608127949738209466313175361161142601108707568
19470026889319648128790363676253707359290547393198350533094409863254710237344552
47692325209744353688541868412075798500629908908768438513508959321262250985142709
19794478379412756202638771417821781240327337108495689300616872374578607430951230
96908870723878513999404242546015617238957825116802801618973562178005776911079790
22026655573872019955677676783191505879571719659770550759779880002320421606755826
75809722478174545846409923210824885805972611279030267270741509747224602604003738
30411365119180944456819762167312738395140461035991994771968906979578667047734952
21981545694935313345331923300019842406900689401417602004228459137311983483386802
30352489602769346000257761959413965109940729263098747702427952104316612809425394
85037536245288888254374135695390839718978818689595231708490351927063849922772653
26064826999661128817511630298712833048667406916285156973335575847429111697259113
53969532522640227276562651123634766230804871160471143157687290382053412295542343
14022687833967461351170188107671919648640149202504369991478703293224727284508796
06843631262345918398240286430644564444566815901074110609701319038586170760771099
41252989796265436701638358088345892387619172572763571929093224171759199798290520
71975442996399826830220944004118266689537930602427572308646745061258472912222347
18088442198837834539211242627770833874751143136048704550494404981971932449150098
52555927020553995188323691320225317096340687798498057634440618188905647503384292
79493920419695886724506109053220167190536026635080266763647744881063220423654648
36855624855494077960732944499038847158715263413026604773216510801253044020991845
89652657529729792772055725210165026891724511953666038764273616212464901231675592
46950937136633665320781952510620087284589083139308516989522633786063418913473703
96532777760440118656525488729217328376766171004246127636983612583177565603918697
15557602015171235214344399010185766876727226408494760175957535995025356361689144
85181975631986409708533731043231896096597038345028523539733981468056497208027899
6245509252811753667386001506195
然而，如果要从该索引返回到前一个实现所表示的900选1000万的组合，这将非常慢（因为它只是在每次迭代中从n中减去1）。
对于如此大量的组合列表，我们可以使用二分搜索空间的方法，虽然增加了一些开销，但对于小型组合列表而言，速度减慢只是很小的。
def iterCombination(index, n, k):
'''Yields the items of the single combination that would be at the provided
(0-based) index in a lexicographically sorted list of combinations of choices
of k items from n items [0,n), given the combinations were sorted in
descending order. Yields in descending order.
'''
if index < 0 or n < k or n < 1 or k < 1 or choose(n, k) <= index:
return
for i in range(k, 0, -1):
d = (n - i) // 2 or 1
n -= d
while 1:
nCi = choose(n, i)
while nCi > index:
d = d // 2 or 1
n -= d
nCi = choose(n, i)
if d == 1:
break
n += d
d //= 2
n -= d
yield n
index -= nCi
从这个中可以看出，所有对choose的调用都有可以抵消的项，如果我们把一切都抵消掉，我们最终得到一个更快的实现，并且是我认为最优解决方案的函数...
该问题的最优函数
def iterCombination(index, n, k):
'''Yields the items of the single combination that would be at the provided
(0-based) index in a lexicographically sorted list of combinations of choices
of k items from n items [0,n), given the combinations were sorted in
descending order. Yields in descending order.
'''
nCk = 1
for nMinusI, iPlus1 in zip(range(n, n - k, -1), range(1, k + 1)):
nCk *= nMinusI
nCk //= iPlus1
curIndex = nCk
for k in range(k, 0, -1):
nCk *= k
nCk //= n
while curIndex - nCk > index:
curIndex -= nCk
nCk *= (n - k)
nCk -= nCk % k
n -= 1
nCk //= n
n -= 1
yield n
最后提醒，在这个问题的使用情况下，你需要做类似这样的操作：
def combinationAt(index, itemsDescending, k):
return [itemsDescending[i] for i in
list(iterCombination(index, len(itemsDescending), k))[-1::-1]]
>>> itemsDescending = [6,4,2,1]
>>> numberOfItemsBeingChosen = 3
>>> zeroBasedIndexWanted = 1
>>> combinationAt(zeroBasedIndexWanted, itemsDescending, numberOfItemsBeingChosen)
[6, 4, 1]
- Jonathan Allan
2
2不错。Stanton和White的一本旧书《构造组合学》中有大量这样的算法。例如——它具有用于生成排列的Johnson-Trotter算法（易于找到），以及用于确定排列在结果排序中的秩的算法（更难找到）。该书使用了类似Pascal的过时伪代码，但很容易将代码翻译成更现代的语言。 - John Coleman
我得找到一份副本！ - Jonathan Allan
8
一种做法是利用比特位的属性。这仍然需要一些枚举，但你不必枚举每个集合。
对于你的例子，集合中有4个数字。因此，如果要生成所有可能的4个数字的组合，则可以按以下方式枚举它们:
{6、4、2、1}
0000 - {(没有数字在集合中)} 0001 - {1} 0010 - {2} 0011 - {2, 1} ... 1111 - {6、4、2、1}
看到了吗？每个“比特位”对应“该数字是否在您的集合中”？我们在这里看到有16种可能性（2^4）。
现在我们可以遍历并找到所有只有3个比特位打开的可能性。这将告诉我们存在的所有“3”的组合：
0111 - {4, 2, 1} 1011 - {6, 2, 1} 1101 - {6, 4, 1} 1110 - {6, 4, 2}
让我们将每个二进制值重写为十进制值：
0111 = 7 1011 = 11 1101 = 13 1110 = 14
既然我们做到了-嗯，你说你想要第“3”个枚举值。那么让我们看看第三个最大的数字：11。它具有比特模式1011。对应... {6、2、1}
酷！
基本上，你可以对任何集合使用相同的概念。现在我们所做的只是将问题从“枚举所有集合”转换为“枚举所有整数”。这对于你的问题可能会更容易一些。
对于你的例子，集合中有4个数字。因此，如果要生成所有可能的4个数字的组合，则可以按以下方式枚举它们:
{6、4、2、1}
0000 - {(没有数字在集合中)} 0001 - {1} 0010 - {2} 0011 - {2, 1} ... 1111 - {6、4、2、1}
看到了吗？每个“比特位”对应“该数字是否在您的集合中”？我们在这里看到有16种可能性（2^4）。
现在我们可以遍历并找到所有只有3个比特位打开的可能性。这将告诉我们存在的所有“3”的组合：
0111 - {4, 2, 1} 1011 - {6, 2, 1} 1101 - {6, 4, 1} 1110 - {6, 4, 2}
让我们将每个二进制值重写为十进制值：
0111 = 7 1011 = 11 1101 = 13 1110 = 14
既然我们做到了-嗯，你说你想要第“3”个枚举值。那么让我们看看第三个最大的数字：11。它具有比特模式1011。对应... {6、2、1}
酷！
基本上，你可以对任何集合使用相同的概念。现在我们所做的只是将问题从“枚举所有集合”转换为“枚举所有整数”。这对于你的问题可能会更容易一些。
- poundifdef
1
3这只是列举了我要找的那个组合之前的所有组合，这恰恰是我不想做的。对于像 5C3 这样的简单问题，它可以正常工作，但如果数字很大，你就会遇到麻烦。 - Sami
4
以下内容来自Python 3.6 itertools recipes:
def nth_combination(iterable, r, index):
'Equivalent to list(combinations(iterable, r))[index]'
pool = tuple(iterable)
n = len(pool)
if r < 0 or r > n:
raise ValueError
c = 1
k = min(r, n-r)
for i in range(1, k+1):
c = c * (n - k + i) // i
if index < 0:
index += c
if index < 0 or index >= c:
raise IndexError
result = []
while r:
c, n, r = c*r//n, n-1, r-1
while index >= c:
index -= c
c, n = c*(n-r)//n, n-1
result.append(pool[-1-n])
return tuple(result)
实际操作中：
iterable, r, index = [6, 4, 2, 1], 3, 2
nth_combination(iterable, r, index)
# (6, 2, 1)
另外，如文档字符串中所述：
import itertools as it
list(it.combinations(iterable, r))[index]
# (6, 2, 1)
另请参阅more_itertools - 一个第三方库，它为您实现了此方法。通过以下方式安装：
> pip install more_itertools
- pylang
2
仅仅是一个简单的草图： 将您的数字排列成元组的上三角矩阵：
A(n-1,n-1)
Aij = [i+1, j-1]
如果您首先按行遍历矩阵，则可以按顺序获得两个元素的组合。要推广到三个元素，请将矩阵行视为另一个三角矩阵，而不是向量。它有点像创建了一个立方体的角落。
至少这是我解决问题的方法。
让我澄清一下，您不必存储矩阵，但需要计算索引。让我解决二维示例，您原则上可以将其扩展到20个维度（记录可能非常糟糕）。
ij = (i*i + i)/2 + j // ij is also the combination number
(i,j) = decompose(ij) // from ij one can recover i,j components
I = i // actual first index
J = j + 1 // actual second index
这个二维示例适用于任何数字n，而且你不必列出排列表格。
- Anycorn
1
抱歉，我不遵循这种方法。比如说，如果我们要对30C20进行操作，那么这是否需要20个维度呢？这是不太可能的。 - Sami
0
有没有一种直接获取nCr的所有组合有序集合中第N个组合的方法？比如说你需要生成给定集合的第0、第3、第6个组合。你可以使用JNumberTools直接生成，而无需生成中间组合。甚至可以生成下一个十亿个组合（如果集合大小很大）。
这是代码示例：
JNumberTools.combinationsOf(list)
.uniqueNth(8,1000_000_000) //skip to billionth combination of size 8
.forEach(System.out::println);
JNumberTools 的 Maven 依赖项为：
<dependency>
<groupId>io.github.deepeshpatel</groupId>
<artifactId>jnumbertools</artifactId>
<version>1.0.0</version>
</dependency>
- Deepesh Patel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接