python - Recursively generate Compositions from an ordered list -

given ordered list of 'n' elements, want slice list generate every distinct permutation of sublists once only, whilst maintaining order of original list - i.e. generate every composition of input list. (this not same calculating every possible combination of possible sublists input list).

for example, given input list [a,b,c,d], output following 8 nested lists:

[[a,b,c,d]], [[a,b,c],[d]], [[a,b],[c,d]], [[a,b],[c],[d]], [[a],[b,c],[d]], [[a],[b],[c,d]], [a,[b,c,d]], [[a],[b],[c],[d]]. 

drawing tree of possible permutations suggests problem lend recursive algorithm, i'm not sure how implement in python maximum speed , efficiency, , grateful advice , guidance.

def composition(seq):     seq = tuple(seq)     in range(2**(len(seq)-1)):         result = [[seq[0]]]         j in range(len(seq)-1):             if & (1<<j):                 result.append([seq[j+1]])             else:                 result[-1].append(seq[j+1])         yield result  if __name__=="__main__":     pprint import pprint     pprint(list(composition('abcd'))) 

reference: https://en.wikipedia.org/wiki/composition_(combinatorics)