N组合
有一种直接的方法来获得nCr所有组合的有序集合的第N个组合吗？
例如：我有四个元素：[6，4，2，1]。 所有可能的组合，一次取三个：[[6,4,2]，[6,4,1]，[6,2,1]，[4,2,1]]。
有没有一个algorithm，可以给我例如第三个答案，[6,2,1]，在有序的结果集，没有列举所有以前的答案？
请注意，您可以通过recursion地生成与第一个元素的所有组合，然后生成所有没有组合的序列。 在这两种recursion的情况下，你放下第一个元素来获得来自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 任何时候通过做出这样的select来生成一个序列，都可以通过计算一个select产生多less个元素并将计数与k进行比较来recursion地生成第k 个元素。 如果k小于计数，则做出该select。 否则，减去计数，并重复其他可能的select，你可以在这一点上。 如果总是有b选项，您可以将其视为以b为基础生成一个数字。 如果select的数量不同，技术仍然有效。 在伪代码中（当所有的select总是可用的）：
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 <= size of choice 。
棘手的部分（以及伪代码中未指定的部分）是select的大小取决于先前的select。 请注意，伪代码可以用来解决比问题更普遍的情况。
对于这个具体问题，有两种select（ b = 2），第一个select的大小（即包括第一个元素）由n-1 C r-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(ki, 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(ki, 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]
一种方法是使用位的属性。 这仍然需要一些枚举，但是你不需要枚举每一组。
举个例子，你有4个数字。 所以，如果你正在产生所有可能的4个数字的组合，你可以列举如下：
{6,4,2,1}
0000 - {（集合中没有数字）}
0001 - {1}
0010 - {2}
0011 - {2，1}
...
1111 - {6,4,2,1}
看看每个“位”是如何对应“这个数字是否在你的设置”？ 我们在这里看到有16种可能性（2 ^ 4）。
所以现在我们可以通过find所有只有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
现在我们已经这样做了 – 呃，你说你想要“第三”枚举。 所以让我们看看第三大的数字：11.其中有位模式1011.它对应于… {6，2，1}
凉！
基本上，你可以使用任何一套相同的概念。 所以现在我们所做的就是把问题从“枚举所有集合”转换成“列举所有整数”。 这可能会更容易解决您的问题。
- TLDR？ 滚动到最后的解决scheme的底部。
我偶然发现了这个问题，同时我正在寻找一些方法来获取指定的组合所在的索引 ，如果它是按照字典顺序排列的列表， 反之亦然 ，可以从一些可能非常大的对象集合中select对象，并且可以对后者没有太多的了解（问题的反面并不是那么难以捉摸）。
既然我也解决了（我的想法是）你确切的问题，我想我会在这里发布我的解决scheme。
**
编辑：我的要求是你的要求太 – 我看到了答案，并认为recursion是好的。 那么现在，经过六年，你已经拥有了。 向下滚动。
**
因为你的要求（我以为是）在这个问题上提出这将做的工作就好了：
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)
下面是我为我的要求（而且真的是为你的！）做的一个非recursionalgorithm，它不创build或遍历任一方向的有序列表，而是使用一个简单而有效的非recursion实现n C r ，select（n，k）：
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
要在正向sorting列表中的某个（从零开始）索引处获取组合：
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
这对你来说太过分了（但是现在我意识到这只是一个例子）。 这是如何为每个指标轮stream：
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
这样可以find一些长列表的索引，或者在一些眨眼的天文索引中返回组合，例如：
>>> 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]
或者，因为这是最后一个，并且由于select（n，k）中的reflection，所以可以是快的，这里是从右边到中间的一个，似乎也是一样快。
>>> 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-10,000,000的组合与以前的实现将会非常缓慢（因为它在每次迭代时简单地从n中减去1）。
对于如此庞大的组合列表，我们可以对空间进行二分search，而我们添加的开销意味着对于小组合列表来说只会稍微慢一些：
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有条款取消，如果我们取消一切，我们最终得到一个更快的实施，是什么，我认为…
这个问题的最佳function
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]
只是一个粗略的草图：把你的数字排列成元组的上三angularmatrix：
A(n-1,n-1) Aij = [i+1, j-1]
如果您首先遍历matrix行，您将获得两个元素递增的组合。 推广到三个要素，把你的matrix行看作是另一个三angular形matrix，而不是一个向量。 这种创build一个立方体的angular落。
至less这是我如何处理这个问题
让我澄清这一点，你不必存储matrix，你将需要计算索引。 让我看看维度的例子，你原则上可以扩展到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，你不必列表排列。
