Перестановки в 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 Мои текущие ограничения: а) я только сейчас изучаю питон (это часть идеи) б) мне придется использовать 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:]

(из эти ребята )

Но я не уверен, как использовать это в моем предложении. Может ли кто-нибудь дать советы и кусочки кода помощи?

ура

е.

Answer 1

Перестановки предназначены для того, чтобы взять упорядоченный набор вещей и переместить эти вещи (то есть изменить порядок).Ваш вопрос касается комбинаций вещей из вашего списка.

Теперь простой способ перечисления комбинаций - это сопоставление записей из вашего списка с битами в числе.Например, предположим, что если установлен бит № 0 (т. Е. 1), то в комбинации участвует число lst[0], если установлен бит № 1, то в комбинации участвует lst[1] и т. Д. Таким образом, числа вдиапазон 0 <= n < 2**(len(lst)) идентифицирует все возможные комбинации lst членов, включая пустой (n = 0) и целое lst (n = 2**(len(lst)) - 1).

Вам нужны только комбинации из 2 или более элементовт.е. только те идентификаторы комбинации, которые имеют по крайней мере два ненулевых бита в своем двоичном представлении.Вот как это определить:

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]

Следующим шагом является извлечение комбинации элементов списка, идентифицируемых идентификатором комбинации.Это легко, благодаря возможности понимания списка:

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

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

Код ниже генерирует все «подмножества» данного списка (кроме пустого набора), то есть возвращает список списков.

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