fork download
copy 
  1. '''http://stackoverflow.com/questions/8347815/generating-combinations-of-a-string-not-permutations/8349358#8349358'''
  2.  
  3.  
  4. def combine0(s):
  5.     out = []
  6.     length = len(s)
  7.     def loc(start):
  8.         for i in range(start, length):
  9.             out.append(s[i])
  10.             print out
  11.             if (i < length-1):
  12.                 loc(i+1)
  13.             del out[-1]
  14.     loc(0)
  15.  
  16.  
  17. def combine1(s):
  18.     #A bit faster than combine2
  19.     out = []
  20.     length = len(s)
  21.     def loc(start):
  22.         for i in range(start, length):
  23.             out.append(s[i])
  24.             yield out
  25.             if (i < length-1):
  26.                 for els in loc(i+1):
  27.                     yield els              
  28.             del out[-1]
  29.     for v in loc(0):
  30.         yield v
  31.  
  32.  
  33. def combine2(s):
  34.     #A bit slower than combine1
  35.     length = len(s)
  36.     def gen(start, prepending=[]): #recursive generator
  37.         if start == length-1:
  38.             yield prepending + [s[start]]
  39.         else:
  40.             for i in range(start,length):
  41.                 current = prepending + [s[i]] #save the current list for reusing
  42.                 yield current
  43.                 for els in gen(i+1,current):
  44.                     yield els
  45.     for v in gen(0):
  46.         yield v
  47.  
  48.  
  49.  
  50. if __name__ == '__main__':
  51.     s = "wxyz"
  52.  
  53.     print('combine0')
  54.     combine0(s)
  55.  
  56.     print('')
  57.     print('combine1')
  58.     for v in combine1(s):
  59.         print(v)
  60.  
  61.     print('')
  62.     print('combine2')    
  63.     for v in combine2(s):
  64.         print(v)
  65.  
  66.  
  67.  
  68.  
  69.     print('')
  70.     print('Efficiency testings')    
  71.     import timeit
  72.     import __main__
  73.  
  74.     N = 1 #Number of executions
  75.  
  76.     s = 'a'*16
  77.  
  78.     f_names = ['combine1','combine2']
  79.  
  80.  
  81.     for f_name in f_names:
  82.  
  83.         init = '''from __main__ import {name}, s'''.format(name=f_name)
  84.         t = timeit.Timer(stmt='[i for i in {name}(s)]'.format(name=f_name),
  85.                          setup=init)
  86.  
  87.         time = t.timeit(N)
  88.         print('{name}: {time}'.format(name=f_name,time=time))
  89.  
Success #stdin #stdout 0.41s 6780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/V3WIM
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!