'''http://stackoverflow.com/questions/8347815/generating-combinations-of-a-string-not-permutations/8349358#8349358''' def combine0(s): out = [] length = len(s) def loc(start): for i in range(start, length): out.append(s[i]) print out if (i < length-1): loc(i+1) del out[-1] loc(0) def combine1(s): #A bit faster than combine2 out = [] length = len(s) def loc(start): for i in range(start, length): out.append(s[i]) yield out if (i < length-1): for els in loc(i+1): yield els del out[-1] for v in loc(0): yield v def combine2(s): #A bit slower than combine1 length = len(s) def gen(start, prepending=[]): #recursive generator if start == length-1: yield prepending + [s[start]] else: for i in range(start,length): current = prepending + [s[i]] #save the current list for reusing yield current for els in gen(i+1,current): yield els for v in gen(0): yield v if __name__ == '__main__': s = "wxyz" print('combine0') combine0(s) print('') print('combine1') for v in combine1(s): print(v) print('') print('combine2') for v in combine2(s): print(v) print('') print('Efficiency testings') import timeit import __main__ N = 1 #Number of executions s = 'a'*16 f_names = ['combine1','combine2'] for f_name in f_names: init = '''from __main__ import {name}, s'''.format(name=f_name) t = timeit.Timer(stmt='[i for i in {name}(s)]'.format(name=f_name), setup=init) time = t.timeit(N) print('{name}: {time}'.format(name=f_name,time=time))
Standard input is empty
combine0 ['w'] ['w', 'x'] ['w', 'x', 'y'] ['w', 'x', 'y', 'z'] ['w', 'x', 'z'] ['w', 'y'] ['w', 'y', 'z'] ['w', 'z'] ['x'] ['x', 'y'] ['x', 'y', 'z'] ['x', 'z'] ['y'] ['y', 'z'] ['z'] combine1 ['w'] ['w', 'x'] ['w', 'x', 'y'] ['w', 'x', 'y', 'z'] ['w', 'x', 'z'] ['w', 'y'] ['w', 'y', 'z'] ['w', 'z'] ['x'] ['x', 'y'] ['x', 'y', 'z'] ['x', 'z'] ['y'] ['y', 'z'] ['z'] combine2 ['w'] ['w', 'x'] ['w', 'x', 'y'] ['w', 'x', 'y', 'z'] ['w', 'x', 'z'] ['w', 'y'] ['w', 'y', 'z'] ['w', 'z'] ['x'] ['x', 'y'] ['x', 'y', 'z'] ['x', 'z'] ['y'] ['y', 'z'] ['z'] Efficiency testings combine1: 0.18497800827 combine2: 0.207851886749