Recipe19.15.Generating Permutations, Combinations, and Selections

Recipe 19.15. Generating Permutations, Combinations, and Selections

Credit: Ulrich Hoffmann, Guy Argo, Danny Yoo, Carl Bray, Doug Zongker, Gagan Saksena, Robin Houston, Michael Davies

Problem

You need to iterate on the permutations, combinations, or selections of a sequence. The fundamental rules of combinatorial arithmetic indicate that the length of these derived sequences are very large even if the starting sequence is of moderate size: for example, there are over 6 billion permutations of a sequence of length 13. So you definitely do not want to compute (and keep in memory) all items in a derived sequence before you start iterating,

Solution

Generators enable you to compute needed objects one by one as you iterate on them. The loop inevitably takes a long time if there are vast numbers of such objects and you really need to examine each one. But at least you do not waste memory storing all of them at once:

def _combinators(_handle, items, n):     ''' factored-out common structure of all following combinators '''     if n==0:         yield [  ]         return     for i, item in enumerate(items):         this_one = [ item ]         for cc in _combinators(_handle, _handle(items, i), n-1):             yield this_one + cc def combinations(items, n):     ''' take n distinct items, order matters '''     def skipIthItem(items, i):         return items[:i] + items[i+1:]     return _combinators(skipIthItem, items, n) def uniqueCombinations(items, n):     ''' take n distinct items, order is irrelevant '''     def afterIthItem(items, i):         return items[i+1:]     return _combinators(afterIthItem, items, n) def selections(items, n):     ''' take n (not necessarily distinct) items, order matters '''     def keepAllItems(items, i):         return items     return _combinators(keepAllItems, items, n) def permutations(items):     ''' take all items, order matters '''     return combinations(items, len(items)) if _ _name_ _=="_ _main_ _":     print "Permutations of 'bar'"     print map(''.join, permutations('bar')) # emits ['bar', 'bra', 'abr', 'arb', 'rba', 'rab']     print "Combinations of 2 letters from 'bar'"     print map(''.join, combinations('bar', 2)) # emits ['ba', 'br', 'ab', 'ar', 'rb', 'ra']     print "Unique Combinations of 2 letters from 'bar'"     print map(''.join, uniqueCombinations('bar', 2)) # emits ['ba', 'br', 'ar']     print "Selections of 2 letters from 'bar'"     print map(''.join, selections('bar', 2)) # emits ['bb', 'ba', 'br', 'ab', 'aa', 'ar', 'rb', 'ra', 'rr']

Discussion

The generators in this recipe accept any sequence as the items argument and always yield lists of length n, where n is the second argument to the generator (permutations accepts only one argument, and n is by definition equal to len(items)).

You can modify the recipe so the generators yield tuples (or instances of another sequence type), instead of lists, by changing two lines of code in _combinators. The yield [ ] must become yield ( ) (more generally, this statement must yield the empty sequence of any sequence type you wish to use), and name this_one must be bound to the Singleton sequence of any sequence type you wish to use. For example, to yield tuples, change the statement that assigns to name this_one into:

    this_one = items[i],

(A subtle, often-forgotten point of Python syntax is that the comma identifies the right side of the assignment as a tuple. Placing parentheses around the right-hand side would be both insufficient and superfluous.)

Another way to modify this recipe is to have the generators yield sequences of the same type as argument items. (As long as this type is indeed a sequence: specifically, it must support slicing, as well as the use of the plus sign, +, for concatenation). If that is what you want, change the yield of the empty sequence into:

    yield items[:0]

and change the assignment to name this_one into:

    this_one = items[i:i+1]

The definition of distinct items for this recipe's purposes is: "items that occur at different indices in the input sequence." If your input sequence has duplicates (i.e., the same item occurring at multiple indices), none of the functions in this recipe will care about removing them: rather, all functions will treat the duplicates as "distinct items" for all purposes.

Recipe19.15.Generating Permutations, Combinations, and Selections