لطفا منتظر باشید ...
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.
See Also
Recipe 19.16 for another
combinatorics building block; Recipe 18.1 and Recipe 18.2.
