Need to Create a new Python List with all possible unique combinations of another list

Question

I currently have a list of choices:

a = ['D1', 
    'C1', 
    'D2', 
    'C2', 
    'D3', 
    'C3', 
    'D4', 
    'C4', 
    'D5', 
    'C5',]

I want a new list with nested lists inside of possible combinations. Like this:

b = [
'D1', 
'C1', 
'D2', 
'C2', 
'D3', 
'C3', 
'D4', 
'C4', 
'D5', 
'C5',
['D1', 'C1'], 
['D1', 'D2'], 
['D1', 'C2'] 
.
. 
['D1', 'C1', 'D2'] 
.
. 
['D1', 'C1', 'D2', 'C2'] 
.
. 
['D1', 'C1', 'D2', 'C2', 'D3']
:
etc

nested loops and different index slices etc, doesn't seem to be the right path to go :/ — Joel Smith, Feb 27 '13 at 17:49
http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python — Waleed Khan, Feb 27 '13 at 17:49

bereal · Answer 1 · 2013-02-27T18:03:23.227

2

Check out itertools.combinations:

b = []
for len_ in xrange(len(a)):
    b.extend(itertools.combinations(a, len_+1)

See also the powerset recipe from the itertools docs:

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

edited Feb 27 '13 at 18:03

answered Feb 27 '13 at 17:57

bereal

32,519
6
58
104

martineau · Answer 2 · 2013-02-28T20:14:52.337

You can create a new list using itertools.combinations in conjunction with a very efficient and relatively succinct construct called a list comprehension. However for doing this it got a little complicated partially by the fact that not all of the items in the final list are themselves not nested lists. I actually suspect having it that way will make it harder for you to process the list later on, but, regardless, here's the simplest implementation I've been able to devise which produces exactly the list you said you wanted:

from itertools import combinations

a = ['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5']
b = [item for sublist in (list(combo[0] if len(combo) < 2 else list(combo)
                               for combo in combinations(a, n))
                                   for n in range(1, len(a)+1)) for item in sublist]

from pprint import pprint  # print the result
print 'b = \\'
pprint(b[:14] + ['... lines omitted ...'] + b[-14:])

Output:

b = \
['D1',
 'C1',
 'D2',
 'C2',
 'D3',
 'C3',
 'D4',
 'C4',
 'D5',
 'C5',
 ['D1', 'C1'],
 ['D1', 'D2'],
 ['D1', 'C2'],
 ['D1', 'D3'],
 '... lines omitted ...',
 ['C1', 'D2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['C1', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5'],
 ['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'C5'],
 ['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'D5', 'C5'],
 ['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'C4', 'D5', 'C5'],
 ['D1', 'C1', 'D2', 'C2', 'D3', 'D4', 'C4', 'D5', 'C5'],
 ['D1', 'C1', 'D2', 'C2', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['D1', 'C1', 'D2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['D1', 'C1', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['D1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5'],
 ['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5']]

+1 I still remember on OS I got answer for my first question from you. The question has been removed. That time I read You have been worked for Nasa! Thanks. — Grijesh Chauhan, Feb 27 '13 at 18:23
@GrijeshChauhan: Greetings again. Yep, sounds like that likely was me. Thanks for the up-vote. Looks like you've come a long way fairly rapidly since then judging by your current rep. — martineau, Feb 28 '13 at 16:26
Yes I remember perfectly. In Q was writing Python equivalent C code to generate MD5's analog seq. function using `sin()` & `abs()` question closed within few-mints because of lack of English and formatting errors But you given idea in comments that there was bitoverflow. I do remember. :) — Grijesh Chauhan, Feb 28 '13 at 16:37

Grijesh Chauhan · Answer 3 · 2013-02-27T18:48:59.487

You need actually power set of a here is my solution:

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

a =['D1', 'C1', 'D2', 'C2', 'D3', 'C3', 'D4', 'C4', 'D5', 'C5']
b = [x for x in powerset(a)]
b.sort(key = len)
for x in b:
 print x

my refrence site: And Its working you can see at codepade here

EDIT a instance of run.

a =['D1', 'C1', 'D2']
b = [x for x in powerset(a)]
b.sort(key = len)
for x in b:
  print x

And its output:

[]
['D2']
['C1']
['D1']
['C1', 'D2']
['D1', 'D2']
['D1', 'C1']
['D1', 'C1', 'D2']

You can find Better code for Powerset in Python from following links.

http://docs.python.org/2/library/itertools.html
http://mail.python.org/pipermail/tutor/2004-April/029413.html
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/

Although Mr.martineau given small and fast code but I don't understand itertools yet.

Rushy Panchal · Answer 4 · 2013-02-27T18:23:54.927

I suggest using itertools.permutations(a).

import itertools
a = ['D1', 
    'C1', 
    'D2', 
    'C2', 
    'D3', 
    'C3', 
    'D4', 
    'C4', 
    'D5', 
    'C5',]

b = list(itertools.permutations(a)) # this gives permutations of the same length

If you want ALL the possible permutations (of varying lengths), you can use a for loop:

b = []
for i in range(1, len(a)+1):
    b.extend(list(itertools.permutations(a, i)))

Put that into a list comprehension:

b = [list(itertools.permutations(x, i)) for i in range(1, len(x)+1)]

Need to Create a new Python List with all possible unique combinations of another list

4 Answers4