tools.py
Go to the documentation of this file.
00001 def cartesian_product(sequences):
00002   # This isn't actually a proper cartesian product because we
00003   # concatenate lists, rather than forming sequences of atomic elements.
00004   if not sequences:
00005     yield []
00006   else:
00007     temp = list(cartesian_product(sequences[1:]))
00008     for item in sequences[0]:
00009       for sequence in temp:
00010         yield item + sequence
00011 
00012 def permutations(alist):
00013   # Note: The list is changed in place as the algorithm is performed.
00014   #       The original value is restored when we are done.
00015   #       Since this is a generator, the caller must be aware
00016   #       of this side effect and copy the input parameter if necessary.
00017   # This is Knuth's "Algorithm P" ("plain changes").
00018   N = len(alist)
00019   if N <= 1:   # Special-case small numbers for speed.
00020     yield alist
00021   elif N == 2:
00022     yield alist
00023     yield [alist[1], alist[0]]
00024   else:
00025     c = [0] * N
00026     d = [1] * N
00027     while True:
00028       yield alist
00029       s = 0
00030       for j in xrange(N - 1, -1, -1):
00031         q = c[j] + d[j]
00032         if q == j + 1:
00033           if j == 0:
00034             return
00035           s += 1
00036         elif q >= 0:
00037           index1, index2 = j - c[j] + s, j - q + s
00038           alist[index1], alist[index2] = alist[index2], alist[index1]
00039           c[j] = q
00040           break
00041         d[j] = -d[j]


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06