Python find ALL combinations of a list

Question

Possible Duplicate:
Power set and Cartesian Product of a set python

scratch the old problem. I figured everything out. Now I have an even crazier issue. Here is what I should be getting:

Input: scoreList(["a", "s", "m", "t", "p"])

output: [['a', 1], ['am', 4], ['at', 2], ['spam', 8]]

This I/O works GREAT, but if I add a 6th element like this:

Input: scoreList(["a", "s", "m", "t", "p", "e"])

The program bugs out like crazy. Please tell me how to fix this. Appreciate any help

My code:

from itertools import chain, combinations

def ind(e,L):
    if L==[] or L=="":
        return 0
    elif L[0]==e:
        return 0
    else:
        return ind(e,L[1:])+1

def letterScore(letter, scorelist):
    if scorelist[0][0] == letter:
        return scorelist[0][1]
    elif (len(scorelist) == 1) and (scorelist[0][0] != letter):
        return 'lol. stop trying to crash my program'
    else:
        return letterScore(letter, scorelist[1:])

scorelist = [ ["a", 1], ["b", 3], ["c", 3], ["d", 2], ["e", 1], ["f", 4], ["g", 2], ["h", 4], ["i", 1], ["j", 8], ["k", 5], ["l", 1], ["m", 3], ["n", 1], ["o", 1], ["p", 3], ["q", 10], ["r", 1], ["s", 1], ["t", 1], ["u", 1], ["v", 4], ["w", 4], ["x", 8], ["y", 4], ["z", 10] ]

def wordScore(S, scorelist):
    if (len(S) == 1):
        return letterScore(S[0],scorelist)
    elif (letterScore(S[0],scorelist) == 'lol. stop trying to crash my program'):
        return 'you really want to crash me, dont you'
    else:
        return letterScore(S[0],scorelist) + wordScore(S[1:], scorelist)


def perm(l):
    sz = len(l)
    if sz <= 1:
        return [l]
    return [p[:i]+[l[0]]+p[i:]
        for i in xrange(sz) for p in perm(l[1:])]


from itertools import combinations, permutations

def findall(my_input):
    return [''.join(p) for x in range(len(my_input)) for c in combinations(my_input, x+1)
            for p in permutations(c)]

d = ["a", "am", "cab", "apple", "at", "bat", "bar", "babble", "can", "foo", "spam", "spammy", "zzyzva"]

def match(lis): 
    return match2(findall(lis))

def match2(lis): 
    if lis == []:
        return []
    elif(len(d) != ind(lis[0],d)):
        return [lis[0]] + match2(lis[1:])
    else:
        return match2(lis[1:])

def scoreList(lis):
    return match3(match(lis))

def match3(lis):
    if (lis == []):
        return []
    else:
        return [[lis[0],wordScore(lis[0],scorelist)]] + match3(lis[1:])

`` is not an error message, it is a textual representation of the generator returned by calling `allperm()`. Iterate over this to retrieve the values. — kindall, Sep 18 '12 at 23:16

score 4 · Answer 1 · edited Sep 18 '12 at 23:27

4

Is this homework, or can you use itertools?

>>> my_input = ['a','b','c']
>>> from itertools import combinations, permutations
>>> [''.join(p) for x in range(len(my_input)) for c in combinations(my_input, x+1)
                for p in permutations(c)]
['a', 'b', 'c', 'ab', 'ba', 'ac', 'ca', 'bc', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

edited Sep 18 '12 at 23:27

Odomontois

15,918
2
36
71

answered Sep 18 '12 at 23:15

John La Rooy

295,403
53
369
502

this is part of a hw so I can not use itertools, but this isnt the whole assignment. This is just the part I am having trouble with – user1681664 Sep 19 '12 at 00:18

score 2 · Answer 2 · edited May 23 '17 at 11:43

2

Probably not the most readable one but here is another solution, using itertools and this answer:

>>> from itertools import permutations
>>> inpt = ['a', 'b', 'c']
>>> sum([map(''.join, list(permutations(inpt, l + 1))) for l in xrange(len(inpt))], [])
['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

edited May 23 '17 at 11:43

Community

1
1

answered Sep 18 '12 at 23:27

Lipis

21,388
20
94
121

Be aware that using `sum()` over lists is discouraged as it has quadratic performance – John La Rooy Sep 19 '12 at 00:35
@gnibbler Yes.. that's why I linked to the other answer :) – Lipis Sep 19 '12 at 06:29

score 1 · Answer 3 · answered Sep 18 '12 at 23:39

1

The earlier answers show the usage of itertools package, but if you don't want to use it (homework is the only reason why you would), I found this algorithm the easiest one to implement.

answered Sep 18 '12 at 23:39

mhaligowski

2,182
20
26

Python find ALL combinations of a list

3 Answers3