Python 2.5.2中的全排列

Question

我有一串数字作为输入，比如：

671.00   
1,636.00
436.00
9,224.00

我想生成所有可能的和，并且给每个和一个标识，输出的时候能看得出来，比如：

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来实现这个功能。 我现在的限制是： a) 我现在正在学习Python（这也是我想做这个的原因） b) 我必须使用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:]

（来自这些人）

但我不太确定怎么把它用在我的需求上。 有人能给我一些建议和代码片段吗？

谢谢，

f.

Answer 1

下面的代码会生成一个给定列表的所有“子集”（除了空集合），也就是说，它会返回一个包含多个列表的列表。

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])

Answer 2

在使用 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)]

Answer 3

排列是指把一组东西按顺序排列并改变它们的位置（也就是改变顺序）。而你问的问题是关于从你的列表中选择组合的内容。

一种简单的方法来列举组合是通过把列表中的每个项映射到一个数字的二进制位上。比如说，如果第0位是1，那么就表示lst[0]这个元素在组合中；如果第1位是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