Welcome, guest | Sign In | My Account | Store | Cart

Efficient recursive functions for generating combinations of specified length from a specified string. Can generate unique or all possible combinations.

Python, 35 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35``` ```#!/usr/bin/env python __version__ = "1.1" """combination.py-- Efficient recursive functions for printing the combination of the selected number of characters from the specified string. Can generate unique or all possible combinations. """ import sys def printList(alist): print ''.join(alist) def printUniqueCombinations(alist, numb, blist=[]): if not numb: return printList(blist) for i in range(len(alist)): blist.append(alist[i]) printUniqueCombinations(alist[i+1:], numb-1, blist) blist.pop() def printCombinations(alist, numb, blist=[]): if not numb: return printList(blist) for i in range(len(alist)): blist.append(alist.pop(i)) printCombinations(alist, numb-1, blist) alist.insert(i, blist.pop()) if __name__ == '__main__': k='love' n=2 if len(sys.argv)>=2: k = sys.argv[1] if len(sys.argv)>=3: n = int(sys.argv[2]) print 'combinations of %d letters in "%s" ' % (n, k) printCombinations(list(k), n) print 'unique combinations of %d letters in "%s" ' % (n, k) printUniqueCombinations(list(k), n) ```

This script supplements the one I wrote for doing permutations of all characters in a string. Like the other one, this uses stacks to print out possible combinations of a selected number of letters from the specified string. It doesn't check for unique letters in the string but can be made to.

I could have coalesed the two functions into one by making the unique option as a parameter to a single function but I think keeping these as two separate functions makes it easy to understand the difference between the two algorithms.

This can be extended for use with arbitrary lists even though the example is with text/strings.

Pierre Johnson 18 years, 9 months ago

String Plucking. First off, thanks for your effort.

Using the string:

``````abcdefghijklmnopqrstuvwxyz
``````

produces an interesting side effect, namely, the script does not self-replicate two-digit combinations, i.e., no aa, bb, cc, dd, ee, ff, ... combinations occur.

Li Daobing 17 years, 2 months ago

A faster printUniqueCombinations. I also post this in http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465

``````def printUniqueCombinations(alist, numb, blist=[]):
if not numb: return printList(blist)
for i in range(len(alist)-numb+1):
blist.append(alist[i])
printUniqueCombinations(alist[i+1:], numb-1, blist)
blist.pop()
``````
Shalabh Chaturvedi 17 years ago

Unique combinations using generators - faster.

``````def getUniqueCombinations(alist, numb):
for i in range(len(alist)):
if numb==1:
yield alist[i]
else:
for combo in getUniqueCombinations(alist[i+1:], numb-1):
yield alist[i] + combo
``````

Note this does not print them but you have to iterate over the result:

``````for combo in getUniqueCombinations('love', 2):
print combo
``````
 Created by Gagan Saksena on Sun, 5 Aug 2001 (PSF)