Permutations en python 2.5.2

Question

J'ai une liste de nombres pour l'entrée, par ex.

671.00 
1,636.00 
436.00 
9,224.00 

et je veux générer toutes les sommes possibles avec un moyen de id pour la sortie, par exemple:

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 
... 

et je voudrais le faire en Python Mes contraintes sont: un) Je suis juste en train d'apprendre python (qui fait partie de l'idée) b) Je vais devoir utiliser Python 2.5.2 (pas intertools)

Je pense que je l'ai trouvé un morceau de code qui peut aider:

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

(de these guys)

Mais je ne sais pas comment l'utiliser dans mon proposer. Quelqu'un pourrait-il donner des conseils et des codes d'aide?

acclamations,

f.

Answer 1

Permutations sont à prendre un ensemble ordonné des choses et le déplacement de ces choses (par exemple pour changer). Votre question porte sur combinaisons de choses de votre liste. Maintenant, un moyen facile d'énumérer des combinaisons est de mapper les entrées de votre liste en bits dans un nombre. Par exemple, supposons que si le bit # 0 est défini (ie 1), alors le numéro lst[0] participe à la combinaison, si le bit # 1 est défini, alors lst[1] participe à la combinaison, etc. De cette façon, les nombres dans la plage 0 <= n < 2**(len(lst)) identifient tous combinaisons possibles de lst membres, y compris un vide (n = 0) et l'ensemble lst (n = 2**(len(lst)) - 1).

Vous n'avez besoin que de combinaisons de 2 éléments ou plus, c'est-à-dire uniquement les ID de combinaison qui ont au moins deux bits différents de zéro dans leur représentation binaire. Voici comment les identifier:

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] 

L'étape suivante consiste à extraire une combinaison de membres de liste identifiés par un identifiant de combinaison.C'est facile, grâce à la puissance de la liste compréhensions:

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] 

Maintenant, nous allons faire un générateur qui produit toutes les sommes, ainsi que leurs représentations de chaîne:

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) 

Et, enfin, nous allons l'utiliser:

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

Le code ci-dessous génère tous les "sous-ensembles" d'une liste donnée (à l'exception de l'ensemble vide), c'est-à-dire qu'il renvoie une liste de listes.

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 

Maintenant, vous pouvez simplement écrire une courte fonction doit pour la sortie aussi:

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

Avec itertools (Python> = 2.6) serait:

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