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

combination (Python recipe) by Gagan Saksena
ActiveState Code (http://code.activestate.com/recipes/66465/)

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

Python, 35 lines
Download
 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.

Tags: algorithms

3 comments

Pierre Johnson 21 years, 2 months ago  # | flag

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 19 years, 7 months ago  # | flag

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 19 years, 5 months ago  # | flag

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