從給定範圍內選擇整數

Question

我需要從range(1, 51)中選擇6個整數，這樣不會選擇兩個連續的整數。 (1, 3, 6, 9, 13, 28)是有效的選擇，但(1, 3, 4, 9, 13, 28)不是。我需要建立一個所有這些可能組合的列表，每個組合都在一個元組中。發電機也可以做，而不是列表。我知道我需要在這裏使用類似itertools.combinations的東西，但我無法弄清楚如何消除連續值的元組。我寫了這個代碼，

>>> import itertools 
>>> l = list(itertools.combinations(range(1, 51), 6)) 
>>> len(l) 
13983816 

也就是說，如果有什麼可以選擇的元組沒有約束我期待的長度，即，50!/(44!6!)。任何幫助？

Answer 1

可以使用all與發電機表達式：

>>> t = (1,3,4,9,13,28) 
>>> all(x-y > 1 for x, y in zip(t[1:], t)) 
False 
>>> t = (1,3,6,9,13,28) 
>>> all(x-y > 1 for x, y in zip(t[1:], t)) 
True 

代碼：

import itertools 
for t in itertools.combinations(range(1, 20), 6): 
    if all(x-y > 1 for x, y in zip(t[1:], t)): 
     #do something with t 

Answer 2

from itertools import combinations, imap 
from operator import add 
from functools import partial 

result = imap(partial(map, add, range(6)), combinations(range(1, 46), 6)) 

該解決方案使得從期望的組合使用的雙射的所述集合中的所有的從1到45的6個整數的組合。我們從1到45中選擇6個遞增的數字x0, x1, x2, x3, x4, x5，然後計算

x0, x1+1, x2+2, x3+3, x4+4, x5+5 

這種新的組合是保證在上述範圍內1-50和沒有連續編號，和任何期望的組合y0, y1, y2, y3, y4, y5可以通過x的獨特的選擇來產生值

y0, y1-1, y2-2, y3-3, y4-4, y5-5 

該作品比基於濾除不需要的組合的解決方案快幾倍。缺點是理解需要更長的時間。我必須爲此寫出大量的解釋，而另一種解決方案更直接。使用更長的組合，該算法將具有顯着的優勢。例如，如果我們選擇16個數字而不是6個，另一個算法將考慮該算法組合數量的1212倍。

Answer 3

如果您考慮一下，您的第一個（最低）值不能是「50中的任何一個」值 - 它必須小於或等於40，因爲(40, 42, 44, 46, 48, 50)是「最後一個有效元組」。在你選擇的那個之間總是有5個「未使用的值」，所以最簡單的方法是從1到45中選擇「無約束」值，然後將0,1,2，... 5加到（排序）值。

因此：

for t in itertools.combinations(range(1,46), 6): 
    print tuple(x+y for x,y in zip(t, (0,1,2,3,4,5))) 

這是更有效的，因爲它不產生它不會使用任何組合。你談論的數字很重要。原始= 50!/(44!*6!)，新= 45!/(39!*6!)。這使得約2倍更有效（50*49*48*47*46*45/(45*44*43*42*41*40)）〜1.95 ...（和感謝user2357112您指出刺目的算術錯誤我犯了 - 曾經有在悄悄的額外因素6! ...）