iterator - Efficient enumeration of ordered subsets in Python -

i'm not sure of appropriate mathematical terminology code i'm trying write. i'd generate combinations of unique integers, "ordered subsets" of each combination used exclude later combinations.

hopefully example make clear:

from itertools import chain, combinations ​ mylist = range(4) max_depth = 3  rev = chain.from_iterable(combinations(mylist, i) in xrange(max_depth, 0, -1)) el in list(rev):     print el 

---

that code results in output contains subsets want, ones not. have manually inserted comments indicate elements don't want.

(0, 1, 2) (0, 1, 3) (0, 2, 3) (1, 2, 3) (0, 1)  # exclude: (0, 1, _) occurs part of (0, 1, 2) above (0, 2)  # exclude: (0, 2, _) occurs above (0, 3)  # keep (1, 2)  # exclude: (1, 2, _) occurs above (1, 3)  # keep: (_, 1, 3) occurs above, (1, 3, _) not (2, 3)  # keep (0,)    # exclude: (0, _, _) occurs above (1,)    # exclude: (1, _, _) occurs above (2,)    # exclude: (2, _) occurs above (3,)    # keep 

---

thus, desired output of generator or iterator be:

(0, 1, 2) (0, 1, 3) (0, 2, 3) (1, 2, 3) (0, 3) (1, 3) (2, 3) (3,)   

i know make list of (wanted , unwanted) combinations , filter out ones don't want, wondering if there more efficient, generator or iterator based way.

you trying exclude combination prefix of previously-returned combination. doing straightforward.

• if tuple t has length max_depth, can't prefix of previously-returned tuple, since tuple it's prefix of have longer.
• if tuple t ends mylist[-1], can't prefix of previously-returned tuple, since there no elements legally added end of t extend it.
• if tuple t has length less max_depth , not end mylist[-1], t prefix of previously-returned tuple t + (mylist[-1],), , t should not returned.

thus, combinations should generate ones of length max_depth , shorter ones end mylist[-1]. following code so, in same order original code, , correctly handling cases maxdepth > len(mylist):

def nonprefix_combinations(iterable, maxlen):     iterable = list(iterable)     if not (iterable , maxlen):         return     comb in combinations(iterable, maxlen):         yield comb     length in xrange(maxlen-2, -1, -1):         comb in combinations(iterable[:-1], length):             yield comb + (iterable[-1],) 

(i've assumed here in case maxdepth == 0, still don't want include empty tuple in output, though maxdepth == 0, isn't prefix of previously-returned tuple. if want empty tuple in case, can change if not (iterable , maxlen) if not iterable.)