Python: Generating all ordered combinations of a list

Question

I'm using Python 2.7.

I'm having a list, and I want all possible ordered combinations.

import itertools
stuff = ["a","b","c", "d"]
for L in range(1, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print( ' '.join(subset))

This will give the following output:

a
b
c
d
a b
a c <-- not in correct order
a d <-- not in correct order
b c
b d <-- not in correct order
c d
a b c
a b d <-- not in correct order
a c d <-- not in correct order
b c d
a b c d

But I want the output only to be combinations that are in the same order as the stuff list. E.g. removing a d, b d, a b d and a c d since these are not in correct order compared to the stuff list ["a", "b", "c", "d"].

I've figured out using this instead:

import itertools
stuff = ["a","b","c", "d"]
for L in range(1, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        if ' '.join(subset) in ' '.join(stuff): #added line
            print( ' '.join(subset))

Is giving me the output I wanted:

a
b
c
d
a b
b c
c d
a b c
b c d
a b c d

But is there any built-in method in Python that does what I want?

Why is a d not in the correct order? What do you mean order? Are you only interested in slices of your original list? And why is a c in correct order when a d is not? — poke
– poke, Commented Jul 23, 2015 at 8:08

poke · Accepted Answer · 2015-07-23 08:41:53Z

I believe what you are looking for are all possible slices of your original list. Your desired output translated into slices is this:

a         # slices[0:1]
b         # slices[1:2]
c         # slices[2:3]
d         # slices[3:4]
a b       # slices[0:2]
b c       # slices[1:3]
c d       # slices[2:4]
a b c     # slices[0:3]
b c d     # slices[1:4]
a b c d   # slices[0:4]

So what you should try to produce are those indexes. And if you look closely and sort them, you can see that those are the 2-combinations of numbers between 0 and 4, where the first number is smaller than the other—which is exactly what itertools.combinations does for a list of indexes. So we can just generate those:

for i, j in itertools.combinations(range(len(stuff) + 1), 2):
    print(stuff[i:j])

This produces the following output:

['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['c']
['c', 'd']
['d']

The advantage is that this produces actual sublists of your input, and doesn’t care if those where single characters in the first place. It can be any kind of content in a list.

If the output order is of any importance, you can order by the output list size to get the desired result:

def getCombinations (lst):
    for i, j in itertools.combinations(range(len(lst) + 1), 2):
        yield lst[i:j]

for x in sorted(getCombinations(stuff), key=len):
    print(' '.join(x))

Elegant code. Maybe the final result need to be sorted, just as in the example output.
@WKPlus That’s a good point, added a way to do that. Thanks! :)
If you use itertools.combinations instead of itertools.permutations, you can omit the if i < j line.
@WKPlus Oh you’re right. I had tested it before but didn’t have the len + 1 part back then and it wasn’t working. Guess I didn’t test it again later… Thanks again! :)

WKPlus · Accepted Answer · 2015-07-23 08:30:26Z

2

I think you mean in continuous order by "in correct order", in this case you just need use two pointers to iterator over stuff:

stuff = ["a","b","c", "d"]
# sort stuff here if it's not sorted

result = []
for i in xrange(len(stuff)):
    for j in xrange(i+1, len(stuff)+1):
        result.append(stuff[i:j])

# sort the result by length, maybe you don't need it
result = sorted(result, key=len)

for r in result:
    print ' '.join(r)

edited Jul 23, 2015 at 8:30

answered Jul 23, 2015 at 8:16

WKPlus

7,3352 gold badges39 silver badges55 bronze badges

3 Comments

TigerhawkT3 Over a year ago

You can replace key=lambda x:len(x) with just key=len.

WKPlus Over a year ago

@TigerhawkT3 Yes, it's more graceful.

amkleist Over a year ago

You are right about I think you mean in continuous order by "in correct order". Thanks for your reply :)

Collectives™ on Stack Overflow

Python: Generating all ordered combinations of a list

2 Answers 2

4 Comments

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

3 Comments

Linked

Related