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?

Answer 1

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)

Answer 2

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