Python中的排列2.5.2

我有一個輸入數字列表，例如Python中的排列2.5.2

，我想產生一個辦法所有可能的資金來標識它的輸出，如：

671.00 + 1,636.00 = 2,307.00 
671.00 + 436.00 = 1,107.00 
671.00 + 9,224.00 = 9,224.00 
671.00 + 1,636.00 + 436.00 = 2,743.00 
...

，我想這樣做在Python 我目前的約束條件是：一）我只是學習蟒蛇現在（這是理念的一部分）二）我將不得不使用Python 2.5.2（無intertools）

我想我已經找到了一段代碼，可以幫助：

def all_perms(str): 
    if len(str) <=1: 
     yield str 
    else: 
     for perm in all_perms(str[1:]): 
      for i in range(len(perm)+1): 
       #nb str[0:1] works in both string and list contexts 
       yield perm[:i] + str[0:1] + perm[i:]

（從these guys）

但我不知道如何在我的建議使用它。有人可以拿出一些提示和幫助代碼嗎？

歡呼聲，

f。

來源

2010-04-22 filippo

http://docs.python.org/library/itertools.html#itertools.permutations與'itertools.permutations'具有相同的代碼 – SilentGhost 2010-04-22 10:19:05

您確定要'636 + 1636'和'1636 + 636'作爲不同的元素？ – kennytm 2010-04-22 10:19:32

我認爲這是*組合*比*排列*。 – 2010-04-22 10:38:57

排列組合是關於採取有序的一套東西，並四處移動這些東西（即切換順序）。你的問題是關於組合你的名單中的東西。

現在，列舉組合的簡單方法是將列表中的條目映射到數字中的位。例如，假設如果位＃0被設置（即1），則編號lst[0]參與組合，如果位＃1被設置，則lst[1]參與組合等。這樣，範圍0 <= n < 2**(len(lst))中的數字標識所有lst成員的可能組合，包括空成員（n = 0）和整個lst（n = 2**(len(lst)) - 1）。

您只需要2項或更多項的組合，即只有組合ID在其二進制表示中至少有兩個非零位。這裏是如何識別這些：

def HasAtLeastTwoBitsSet(x) : 
    return (x & (x-1)) != 0 

# Testing: 
>>> [x for x in range(33) if HasAtLeastTwoBitsSet(x)] 
[3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]

下一步是提取由組合id標識的列表成員的組合。這是很容易，這要歸功於列表內涵的力量：

def GetSublistByCombination(lst, combination_id) : 
    res = [x for (i,x) in enumerate(lst) if combination_id & (1 << i)] 
    return res 

# Testing: 
>>> GetSublistByCombination([0,1,2,3], 1) 
[0] 
>>> GetSublistByCombination([0,1,2,3], 3) 
[0, 1] 
>>> GetSublistByCombination([0,1,2,3], 12) 
[2, 3] 
>>> GetSublistByCombination([0,1,2,3], 15) 
[0, 1, 2, 3]

現在讓我們做一臺發電機，與他們的字符串表示產生的所有款項，一起：

def IterAllSums(lst) : 
    combinations = [i for i in range(1 << len(lst)) if HasAtLeastTwoBitsSet(i)] 
    for comb in combinations : 
     sublist = GetSublistByCombination(lst, comb) 
     sum_str = '+'.join(map(str, sublist)) 
     sum_val = sum(sublist) 
     yield (sum_str, sum_val)

最後，讓我們使用它：

>>> for sum_str, sum_val in IterAllSums([1,2,3,4]) : print sum_str, sum_val 

1+2 3 
1+3 4 
2+3 5 
1+2+3 6 
1+4 5 
2+4 6 
1+2+4 7 
3+4 7 
1+3+4 8 
2+3+4 9 
1+2+3+4 10

來源

2010-04-22 12:09:25 atzz

下面的代碼生成給定列表的所有「子集」（空集除外），即它返回列表的列表。

def all_sums(l): #assumes that l is non-empty 
    if len(l)==1: 
     return ([[l[0]]]) 
    if len(l)==0: 
     return [] 
    result = [] 
    for i in range(0,len(l)): 
     result.append([l[i]]) 
     for p in all_sums(l[i+1:]): 
      result.append([l[i]]+p) 
    return result

現在，你可以只寫一個簡短的功能doit輸出也：

def doit(l): 
    mylist = all_sums(l) 
    print mylist 
    for i in mylist: 
     print str(i) + " = " + str(sum(i)) 

doit([1,2,3,4])

來源

2010-04-22 11:03:46 phimuemue

隨着itertools（Python的> = 2.6）將是：

from itertools import * 
a=[1,2,3,4] 
sumVal=[tuple(imap(sum,combinations(a,i))) for i in range(2,len(a)+1)]

來源

2010-04-22 12:29:57 zoli2k

Python中的排列2.5.2

回答

相關問題