def spanningsets(items): if not items: yield [] return def gen(pos): if pos==0: yield [[items[0]]] #first element makes only one set return for ss in gen(pos-1): #generate for all but the last element yield ss[:] + [[items[pos]]] #add the last element to the ss as a separate element for i,_ in enumerate(ss): yield ss[:i] + [ss[i] + [items[pos]]] + ss[i+1:] #add the last element to each subset of ss for out in gen(len(items)-1): yield out for sset in spanningsets([1, 2, 3, 4]): print(' '.join(map(str, sset)))
Standard input is empty
[1] [2] [3] [4] [1, 4] [2] [3] [1] [2, 4] [3] [1] [2] [3, 4] [1, 3] [2] [4] [1, 3, 4] [2] [1, 3] [2, 4] [1] [2, 3] [4] [1, 4] [2, 3] [1] [2, 3, 4] [1, 2] [3] [4] [1, 2, 4] [3] [1, 2] [3, 4] [1, 2, 3] [4] [1, 2, 3, 4]