python - 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(无互用工具)

我想我找到了一段可能有帮助的代码:

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.

Answer 1

排列是指获取一组有序的事物并移动这些事物(即改变顺序)。您的问题是关于列表中的内容的组合。

现在，枚举组合的一种简单方法是将列表中的条目映射到数字中的位。例如，假设如果设置了位 #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