Перестановки в 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:] 

(от these guys)

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

cheers,

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-х элементов или более, то есть только те комбинации идентификаторов, у которых есть как минимум два ненулевых бита в их двоичном представлении. Вот как их идентифицировать:

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

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

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 3

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