2 Let's try a simple generator:
18 "Falling off the end" stops the generator:
21 Traceback (most recent call last):
22 File "<stdin>", line 1, in ?
23 File "<stdin>", line 2, in g
26 "return" also stops the generator:
31 ... yield 2 # never reached
37 Traceback (most recent call last):
38 File "<stdin>", line 1, in ?
39 File "<stdin>", line 3, in f
41 >>> g.next() # once stopped, can't be resumed
42 Traceback (most recent call last):
43 File "<stdin>", line 1, in ?
46 "raise StopIteration" stops the generator too:
50 ... raise StopIteration
51 ... yield 2 # never reached
57 Traceback (most recent call last):
58 File "<stdin>", line 1, in ?
61 Traceback (most recent call last):
62 File "<stdin>", line 1, in ?
65 However, they are not exactly equivalent:
78 ... raise StopIteration
84 This may be surprising at first:
95 Let's create an alternate range() function implemented as a generator:
98 ... for i in range(n):
104 Generators always return to the most recent caller:
108 ... print "creator", r.next()
114 ... print "caller", i
123 Generators can call other generators:
126 ... for i in yrange(n):
134 # The examples from PEP 255.
140 Restriction: A generator cannot be resumed while it is actively
148 Traceback (most recent call last):
150 File "<string>", line 2, in g
151 ValueError: generator already executing
153 Specification: Return
155 Note that return isn't always equivalent to raising StopIteration: the
156 difference lies in how enclosing try/except constructs are treated.
167 because, as in any function, return simply exits, but
171 ... raise StopIteration
177 because StopIteration is captured by a bare "except", as is any
180 Specification: Generators and Exception Propagation
185 ... yield f() # the zero division exception propagates
186 ... yield 42 # and we'll never get here
189 Traceback (most recent call last):
190 File "<stdin>", line 1, in ?
191 File "<stdin>", line 2, in g
192 File "<stdin>", line 2, in f
193 ZeroDivisionError: integer division or modulo by zero
194 >>> k.next() # and the generator cannot be resumed
195 Traceback (most recent call last):
196 File "<stdin>", line 1, in ?
200 Specification: Try/Except/Finally
208 ... yield 3 # never get here
209 ... except ZeroDivisionError:
215 ... yield 7 # the "raise" above stops this
225 [1, 2, 4, 5, 8, 9, 10, 11]
228 Guido's binary tree example.
230 >>> # A binary tree class.
233 ... def __init__(self, label, left=None, right=None):
234 ... self.label = label
236 ... self.right = right
238 ... def __repr__(self, level=0, indent=" "):
239 ... s = level*indent + repr(self.label)
241 ... s = s + "\\n" + self.left.__repr__(level+1, indent)
243 ... s = s + "\\n" + self.right.__repr__(level+1, indent)
246 ... def __iter__(self):
247 ... return inorder(self)
249 >>> # Create a Tree from a list.
255 ... return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
257 >>> # Show it off: create a tree.
258 >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
260 >>> # A recursive generator that generates Tree labels in in-order.
263 ... for x in inorder(t.left):
266 ... for x in inorder(t.right):
269 >>> # Show it off: create a tree.
270 >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
271 >>> # Print the nodes of the tree in in-order.
274 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
276 >>> # A non-recursive generator.
277 >>> def inorder(node):
281 ... stack.append(node)
284 ... while not node.right:
286 ... node = stack.pop()
287 ... except IndexError:
290 ... node = node.right
292 >>> # Exercise the non-recursive generator.
295 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
299 # Examples from Iterator-List and Python-Dev and c.l.py.
303 The difference between yielding None and returning it.
306 ... for i in range(3):
311 [None, None, None, None]
313 Ensure that explicitly raising StopIteration acts like any other exception
314 in try/except, not like a return.
319 ... raise StopIteration
326 Next one was posted to c.l.py.
329 ... "Generate all combinations of k elements from list x."
336 ... first, rest = x[0], x[1:]
337 ... # A combination does or doesn't contain first.
338 ... # If it does, the remainder is a k-1 comb of rest.
339 ... for c in gcomb(rest, k-1):
340 ... c.insert(0, first)
342 ... # If it doesn't contain first, it's a k comb of rest.
343 ... for c in gcomb(rest, k):
346 >>> seq = range(1, 5)
347 >>> for k in range(len(seq) + 2):
348 ... print "%d-combs of %s:" % (k, seq)
349 ... for c in gcomb(seq, k):
351 0-combs of [1, 2, 3, 4]:
353 1-combs of [1, 2, 3, 4]:
358 2-combs of [1, 2, 3, 4]:
365 3-combs of [1, 2, 3, 4]:
370 4-combs of [1, 2, 3, 4]:
372 5-combs of [1, 2, 3, 4]:
374 From the Iterators list, about the types of these things.
384 >>> [s for s in dir(i) if not s.startswith('_')]
385 ['close', 'gi_code', 'gi_frame', 'gi_running', 'next', 'send', 'throw']
386 >>> print i.next.__doc__
387 x.next() -> the next value, or raise StopIteration
391 >>> isinstance(i, types.GeneratorType)
394 And more, added later.
400 >>> i.gi_running = 42
401 Traceback (most recent call last):
403 TypeError: readonly attribute
405 ... yield me.gi_running
414 A clever union-find implementation from c.l.py, due to David Eppstein.
415 Sent: Friday, June 29, 2001 12:16 PM
416 To: python-list@python.org
417 Subject: Re: PEP 255: Simple Generators
419 >>> class disjointSet:
420 ... def __init__(self, name):
422 ... self.parent = None
423 ... self.generator = self.generate()
425 ... def generate(self):
426 ... while not self.parent:
428 ... for x in self.parent.generator:
432 ... return self.generator.next()
434 ... def union(self, parent):
436 ... raise ValueError("Sorry, I'm not a root!")
437 ... self.parent = parent
439 ... def __str__(self):
442 >>> names = "ABCDEFGHIJKLM"
443 >>> sets = [disjointSet(name) for name in names]
447 >>> gen = random.WichmannHill(42)
450 ... print "%s->%s" % (s, s.find()),
452 ... if len(roots) > 1:
453 ... s1 = gen.choice(roots)
455 ... s2 = gen.choice(roots)
457 ... print "merged", s1, "into", s2
460 A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
462 A->A B->B C->C D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M
464 A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M
466 A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->A M->M
468 A->A B->B C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M
470 A->A B->E C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M
472 A->A B->E C->F D->G E->E F->F G->G H->E I->I J->G K->K L->A M->M
474 A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->M
476 A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->G
478 A->A B->G C->F D->G E->G F->F G->G H->G I->K J->G K->K L->A M->G
480 A->A B->G C->F D->G E->G F->F G->G H->G I->A J->G K->A L->A M->G
482 A->A B->G C->A D->G E->G F->A G->G H->G I->A J->G K->A L->A M->G
484 A->G B->G C->G D->G E->G F->G G->G H->G I->G J->G K->G L->G M->G
489 # Fun tests (for sufficiently warped notions of "fun").
493 Build up to a recursive Sieve of Eratosthenes generator.
495 >>> def firstn(g, n):
496 ... return [g.next() for i in range(n)]
503 >>> firstn(intsfrom(5), 7)
504 [5, 6, 7, 8, 9, 10, 11]
506 >>> def exclude_multiples(n, ints):
511 >>> firstn(exclude_multiples(3, intsfrom(1)), 6)
515 ... prime = ints.next()
517 ... not_divisible_by_prime = exclude_multiples(prime, ints)
518 ... for p in sieve(not_divisible_by_prime):
521 >>> primes = sieve(intsfrom(2))
522 >>> firstn(primes, 20)
523 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
526 Another famous problem: generate all integers of the form
528 in increasing order, where i,j,k >= 0. Trickier than it may look at first!
529 Try writing it without generators, and correctly, and without generating
530 3 internal results for each result output.
535 >>> firstn(times(10, intsfrom(1)), 10)
536 [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
553 The following works, but is doing a whale of a lot of redundant work --
554 it's not clear how to get the internal uses of m235 to share a single
555 generator. Note that me_times2 (etc) each need to see every element in the
556 result sequence. So this is an example where lazy lists are more natural
557 (you can look at the head of a lazy list any number of times).
561 ... me_times2 = times(2, m235())
562 ... me_times3 = times(3, m235())
563 ... me_times5 = times(5, m235())
564 ... for i in merge(merge(me_times2,
569 Don't print "too many" of these -- the implementation above is extremely
570 inefficient: each call of m235() leads to 3 recursive calls, and in
571 turn each of those 3 more, and so on, and so on, until we've descended
572 enough levels to satisfy the print stmts. Very odd: when I printed 5
573 lines of results below, this managed to screw up Win98's malloc in "the
574 usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting
575 address space, and it *looked* like a very slow leak.
578 >>> for i in range(3):
579 ... print firstn(result, 15)
580 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
581 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
582 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
584 Heh. Here's one way to get a shared list, complete with an excruciating
585 namespace renaming trick. The *pretty* part is that the times() and merge()
586 functions can be reused as-is, because they only assume their stream
587 arguments are iterable -- a LazyList is the same as a generator to times().
590 ... def __init__(self, g):
592 ... self.fetch = g.next
594 ... def __getitem__(self, i):
595 ... sofar, fetch = self.sofar, self.fetch
596 ... while i >= len(sofar):
597 ... sofar.append(fetch())
602 ... # Gack: m235 below actually refers to a LazyList.
603 ... me_times2 = times(2, m235)
604 ... me_times3 = times(3, m235)
605 ... me_times5 = times(5, m235)
606 ... for i in merge(merge(me_times2,
611 Print as many of these as you like -- *this* implementation is memory-
614 >>> m235 = LazyList(m235())
615 >>> for i in range(5):
616 ... print [m235[j] for j in range(15*i, 15*(i+1))]
617 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
618 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
619 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
620 [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
621 [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
623 Ye olde Fibonacci generator, LazyList style.
625 >>> def fibgen(a, b):
629 ... yield g.next() + h.next()
632 ... g.next() # throw first away
638 ... for s in sum(iter(fib),
639 ... tail(iter(fib))):
642 >>> fib = LazyList(fibgen(1, 2))
643 >>> firstn(iter(fib), 17)
644 [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
647 Running after your tail with itertools.tee (new in version 2.4)
649 The algorithms "m235" (Hamming) and Fibonacci presented above are both
650 examples of a whole family of FP (functional programming) algorithms
651 where a function produces and returns a list while the production algorithm
652 suppose the list as already produced by recursively calling itself.
653 For these algorithms to work, they must:
655 - produce at least a first element without presupposing the existence of
657 - produce their elements in a lazy manner
659 To work efficiently, the beginning of the list must not be recomputed over
660 and over again. This is ensured in most FP languages as a built-in feature.
661 In python, we have to explicitly maintain a list of already computed results
662 and abandon genuine recursivity.
664 This is what had been attempted above with the LazyList class. One problem
665 with that class is that it keeps a list of all of the generated results and
666 therefore continually grows. This partially defeats the goal of the generator
667 concept, viz. produce the results only as needed instead of producing them
668 all and thereby wasting memory.
670 Thanks to itertools.tee, it is now clear "how to get the internal uses of
671 m235 to share a single generator".
673 >>> from itertools import tee
677 ... for n in merge(times(2, m2),
678 ... merge(times(3, m3),
682 ... m2, m3, m5, mRes = tee(m1, 4)
686 >>> for i in range(5):
687 ... print firstn(it, 15)
688 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
689 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
690 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
691 [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
692 [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
694 The "tee" function does just what we want. It internally keeps a generated
695 result for as long as it has not been "consumed" from all of the duplicated
696 iterators, whereupon it is deleted. You can therefore print the hamming
697 sequence during hours without increasing memory usage, or very little.
699 The beauty of it is that recursive running-after-their-tail FP algorithms
700 are quite straightforwardly expressed with this Python idiom.
702 Ye olde Fibonacci generator, tee style.
708 ... yield g.next() + h.next()
713 ... fibTail.next() # throw first away
714 ... for res in _isum(fibHead, fibTail):
718 ... fibHead, fibTail, fibRes = tee(realfib, 3)
721 >>> firstn(fib(), 17)
722 [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
726 # syntax_tests mostly provokes SyntaxErrors. Also fiddling with #if 0
734 Traceback (most recent call last):
736 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[0]>, line 3)
741 Traceback (most recent call last):
743 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[1]>, line 3)
745 "return None" is not the same as "return" in a generator:
750 Traceback (most recent call last):
752 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[2]>, line 3)
770 ... except ZeroDivisionError:
782 ... except ZeroDivisionError:
827 ... except SyntaxError:
833 ... yield 2 # don't blink
854 ... def __init__(self):
872 ... lambda x: x # shouldn't trigger here
875 ... return 2*i # or here
877 ... return 3 # but *this* sucks (line 8)
879 ... yield 2 # because it's a generator (line 10)
880 Traceback (most recent call last):
881 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[24]>, line 10)
883 This one caused a crash (see SF bug 567538):
886 ... for i in range(3):
900 Traceback (most recent call last):
904 Test the gi_code attribute
910 >>> g.gi_code is f.func_code
915 Traceback (most recent call last):
917 >>> g.gi_code is f.func_code
922 # conjoin is a simple backtracking generator, named in honor of Icon's
923 # "conjunction" control structure. Pass a list of no-argument functions
924 # that return iterable objects. Easiest to explain by example: assume the
925 # function list [x, y, z] is passed. Then conjoin acts like:
928 # values = [None] * 3
929 # for values[0] in x():
930 # for values[1] in y():
931 # for values[2] in z():
934 # So some 3-lists of values *may* be generated, each time we successfully
935 # get into the innermost loop. If an iterator fails (is exhausted) before
936 # then, it "backtracks" to get the next value from the nearest enclosing
937 # iterator (the one "to the left"), and starts all over again at the next
938 # slot (pumps a fresh iterator). Of course this is most useful when the
939 # iterators have side-effects, so that which values *can* be generated at
940 # each slot depend on the values iterated at previous slots.
944 values
= [None] * len(gs
)
946 def gen(i
, values
=values
):
950 for values
[i
] in gs
[i
]():
957 # That works fine, but recursing a level and checking i against len(gs) for
958 # each item produced is inefficient. By doing manual loop unrolling across
959 # generator boundaries, it's possible to eliminate most of that overhead.
960 # This isn't worth the bother *in general* for generators, but conjoin() is
961 # a core building block for some CPU-intensive generator applications.
968 # Do one loop nest at time recursively, until the # of loop nests
969 # remaining is divisible by 3.
971 def gen(i
, values
=values
):
977 for values
[i
] in gs
[i
]():
985 # Do three loop nests at a time, recursing only if at least three more
986 # remain. Don't call directly: this is an internal optimization for
989 def _gen3(i
, values
=values
):
990 assert i
< n
and (n
-i
) % 3 == 0
991 ip1
, ip2
, ip3
= i
+1, i
+2, i
+3
992 g
, g1
, g2
= gs
[i
: ip3
]
995 # These are the last three, so we can yield values directly.
996 for values
[i
] in g():
997 for values
[ip1
] in g1():
998 for values
[ip2
] in g2():
1002 # At least 6 loop nests remain; peel off 3 and recurse for the
1004 for values
[i
] in g():
1005 for values
[ip1
] in g1():
1006 for values
[ip2
] in g2():
1007 for x
in _gen3(ip3
):
1013 # And one more approach: For backtracking apps like the Knight's Tour
1014 # solver below, the number of backtracking levels can be enormous (one
1015 # level per square, for the Knight's Tour, so that e.g. a 100x100 board
1016 # needs 10,000 levels). In such cases Python is likely to run out of
1017 # stack space due to recursion. So here's a recursion-free version of
1019 # NOTE WELL: This allows large problems to be solved with only trivial
1020 # demands on stack space. Without explicitly resumable generators, this is
1021 # much harder to achieve. OTOH, this is much slower (up to a factor of 2)
1022 # than the fancy unrolled recursive conjoin.
1024 def flat_conjoin(gs
): # rename to conjoin to run tests with this instead
1028 _StopIteration
= StopIteration # make local because caught a *lot*
1034 it
= iters
[i
] = gs
[i
]().next
1037 except _StopIteration
:
1043 # Backtrack until an older iterator can be resumed.
1047 values
[i
] = iters
[i
]()
1048 # Success! Start fresh at next level.
1051 except _StopIteration
:
1052 # Continue backtracking.
1058 # A conjoin-based N-Queens solver.
1061 def __init__(self
, n
):
1065 # Assign a unique int to each column and diagonal.
1066 # columns: n of those, range(n).
1067 # NW-SE diagonals: 2n-1 of these, i-j unique and invariant along
1068 # each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0-
1070 # NE-SW diagonals: 2n-1 of these, i+j unique and invariant along
1071 # each, smallest i+j is 0, largest is 2n-2.
1073 # For each square, compute a bit vector of the columns and
1074 # diagonals it covers, and for each row compute a function that
1075 # generates the possiblities for the columns in that row.
1076 self
.rowgenerators
= []
1078 rowuses
= [(1L << j
) |
# column ordinal
1079 (1L << (n
+ i
-j
+ n
-1)) |
# NW-SE ordinal
1080 (1L << (n
+ 2*n
-1 + i
+j
)) # NE-SW ordinal
1083 def rowgen(rowuses
=rowuses
):
1086 if uses
& self
.used
== 0:
1091 self
.rowgenerators
.append(rowgen
)
1093 # Generate solutions.
1096 for row2col
in conjoin(self
.rowgenerators
):
1099 def printsolution(self
, row2col
):
1101 assert n
== len(row2col
)
1102 sep
= "+" + "-+" * n
1105 squares
= [" " for j
in range(n
)]
1106 squares
[row2col
[i
]] = "Q"
1107 print "|" + "|".join(squares
) + "|"
1110 # A conjoin-based Knight's Tour solver. This is pretty sophisticated
1111 # (e.g., when used with flat_conjoin above, and passing hard=1 to the
1112 # constructor, a 200x200 Knight's Tour was found quickly -- note that we're
1113 # creating 10s of thousands of generators then!), and is lengthy.
1116 def __init__(self
, m
, n
, hard
=0):
1117 self
.m
, self
.n
= m
, n
1119 # solve() will set up succs[i] to be a list of square #i's
1121 succs
= self
.succs
= []
1123 # Remove i0 from each of its successor's successor lists, i.e.
1124 # successors can't go back to i0 again. Return 0 if we can
1125 # detect this makes a solution impossible, else return 1.
1127 def remove_from_successors(i0
, len=len):
1128 # If we remove all exits from a free square, we're dead:
1129 # even if we move to it next, we can't leave it again.
1130 # If we create a square with one exit, we must visit it next;
1131 # else somebody else will have to visit it, and since there's
1132 # only one adjacent, there won't be a way to leave it again.
1133 # Finelly, if we create more than one free square with a
1134 # single exit, we can only move to one of them next, leaving
1135 # the other one a dead end.
1145 return ne0
== 0 and ne1
< 2
1147 # Put i0 back in each of its successor's successor lists.
1149 def add_to_successors(i0
):
1153 # Generate the first move.
1158 # Since we're looking for a cycle, it doesn't matter where we
1159 # start. Starting in a corner makes the 2nd move easy.
1160 corner
= self
.coords2index(0, 0)
1161 remove_from_successors(corner
)
1162 self
.lastij
= corner
1164 add_to_successors(corner
)
1166 # Generate the second moves.
1168 corner
= self
.coords2index(0, 0)
1169 assert self
.lastij
== corner
# i.e., we started in the corner
1172 assert len(succs
[corner
]) == 2
1173 assert self
.coords2index(1, 2) in succs
[corner
]
1174 assert self
.coords2index(2, 1) in succs
[corner
]
1175 # Only two choices. Whichever we pick, the other must be the
1176 # square picked on move m*n, as it's the only way to get back
1177 # to (0, 0). Save its index in self.final so that moves before
1178 # the last know it must be kept free.
1179 for i
, j
in (1, 2), (2, 1):
1180 this
= self
.coords2index(i
, j
)
1181 final
= self
.coords2index(3-i
, 3-j
)
1184 remove_from_successors(this
)
1185 succs
[final
].append(corner
)
1188 succs
[final
].remove(corner
)
1189 add_to_successors(this
)
1191 # Generate moves 3 thru m*n-1.
1192 def advance(len=len):
1193 # If some successor has only one exit, must take it.
1194 # Else favor successors with fewer exits.
1196 for i
in succs
[self
.lastij
]:
1198 assert e
> 0, "else remove_from_successors() pruning flawed"
1200 candidates
= [(e
, i
)]
1202 candidates
.append((e
, i
))
1206 for e
, i
in candidates
:
1208 if remove_from_successors(i
):
1211 add_to_successors(i
)
1213 # Generate moves 3 thru m*n-1. Alternative version using a
1214 # stronger (but more expensive) heuristic to order successors.
1215 # Since the # of backtracking levels is m*n, a poor move early on
1216 # can take eons to undo. Smallest square board for which this
1217 # matters a lot is 52x52.
1218 def advance_hard(vmid
=(m
-1)/2.0, hmid
=(n
-1)/2.0, len=len):
1219 # If some successor has only one exit, must take it.
1220 # Else favor successors with fewer exits.
1221 # Break ties via max distance from board centerpoint (favor
1222 # corners and edges whenever possible).
1224 for i
in succs
[self
.lastij
]:
1226 assert e
> 0, "else remove_from_successors() pruning flawed"
1228 candidates
= [(e
, 0, i
)]
1230 i1
, j1
= self
.index2coords(i
)
1231 d
= (i1
- vmid
)**2 + (j1
- hmid
)**2
1232 candidates
.append((e
, -d
, i
))
1236 for e
, d
, i
in candidates
:
1238 if remove_from_successors(i
):
1241 add_to_successors(i
)
1243 # Generate the last move.
1245 assert self
.final
in succs
[self
.lastij
]
1249 self
.squaregenerators
= [first
]
1251 self
.squaregenerators
= [first
, second
] + \
1252 [hard
and advance_hard
or advance
] * (m
*n
- 3) + \
1255 def coords2index(self
, i
, j
):
1256 assert 0 <= i
< self
.m
1257 assert 0 <= j
< self
.n
1258 return i
* self
.n
+ j
1260 def index2coords(self
, index
):
1261 assert 0 <= index
< self
.m
* self
.n
1262 return divmod(index
, self
.n
)
1264 def _init_board(self
):
1267 m
, n
= self
.m
, self
.n
1268 c2i
= self
.coords2index
1270 offsets
= [( 1, 2), ( 2, 1), ( 2, -1), ( 1, -2),
1271 (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
1275 s
= [c2i(i
+io
, j
+jo
) for io
, jo
in offsets
1276 if 0 <= i
+io
< m
and
1280 # Generate solutions.
1283 for x
in conjoin(self
.squaregenerators
):
1286 def printsolution(self
, x
):
1287 m
, n
= self
.m
, self
.n
1288 assert len(x
) == m
*n
1290 format
= "%" + str(w
) + "d"
1292 squares
= [[None] * n
for i
in range(m
)]
1295 i1
, j1
= self
.index2coords(i
)
1296 squares
[i1
][j1
] = format
% k
1299 sep
= "+" + ("-" * w
+ "+") * n
1303 print "|" + "|".join(row
) + "|"
1308 Generate the 3-bit binary numbers in order. This illustrates dumbest-
1309 possible use of conjoin, just to generate the full cross-product.
1311 >>> for c in conjoin([lambda: iter((0, 1))] * 3):
1322 For efficiency in typical backtracking apps, conjoin() yields the same list
1323 object each time. So if you want to save away a full account of its
1324 generated sequence, you need to copy its results.
1326 >>> def gencopy(iterator):
1327 ... for x in iterator:
1330 >>> for n in range(10):
1331 ... all = list(gencopy(conjoin([lambda: iter((0, 1))] * n)))
1332 ... print n, len(all), all[0] == [0] * n, all[-1] == [1] * n
1344 And run an 8-queens solver.
1349 >>> for row2col in q.solve():
1351 ... if count <= LIMIT:
1352 ... print "Solution", count
1353 ... q.printsolution(row2col)
1391 >>> print count, "solutions in all."
1392 92 solutions in all.
1394 And run a Knight's Tour on a 10x10 board. Note that there are about
1395 20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion.
1397 >>> k = Knights(10, 10)
1400 >>> for x in k.solve():
1402 ... if count <= LIMIT:
1403 ... print "Solution", count
1404 ... k.printsolution(x)
1408 +---+---+---+---+---+---+---+---+---+---+
1409 | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8|
1410 +---+---+---+---+---+---+---+---+---+---+
1411 | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11|
1412 +---+---+---+---+---+---+---+---+---+---+
1413 | 59|100| 73| 36| 41| 56| 39| 32| 9| 6|
1414 +---+---+---+---+---+---+---+---+---+---+
1415 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
1416 +---+---+---+---+---+---+---+---+---+---+
1417 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
1418 +---+---+---+---+---+---+---+---+---+---+
1419 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
1420 +---+---+---+---+---+---+---+---+---+---+
1421 | 87| 98| 91| 80| 77| 84| 53| 46| 65| 44|
1422 +---+---+---+---+---+---+---+---+---+---+
1423 | 90| 23| 88| 95| 70| 79| 68| 83| 14| 17|
1424 +---+---+---+---+---+---+---+---+---+---+
1425 | 97| 92| 21| 78| 81| 94| 19| 16| 45| 66|
1426 +---+---+---+---+---+---+---+---+---+---+
1427 | 22| 89| 96| 93| 20| 69| 82| 67| 18| 15|
1428 +---+---+---+---+---+---+---+---+---+---+
1430 +---+---+---+---+---+---+---+---+---+---+
1431 | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8|
1432 +---+---+---+---+---+---+---+---+---+---+
1433 | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11|
1434 +---+---+---+---+---+---+---+---+---+---+
1435 | 59|100| 73| 36| 41| 56| 39| 32| 9| 6|
1436 +---+---+---+---+---+---+---+---+---+---+
1437 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
1438 +---+---+---+---+---+---+---+---+---+---+
1439 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
1440 +---+---+---+---+---+---+---+---+---+---+
1441 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
1442 +---+---+---+---+---+---+---+---+---+---+
1443 | 87| 98| 89| 80| 77| 84| 53| 46| 65| 44|
1444 +---+---+---+---+---+---+---+---+---+---+
1445 | 90| 23| 92| 95| 70| 79| 68| 83| 14| 17|
1446 +---+---+---+---+---+---+---+---+---+---+
1447 | 97| 88| 21| 78| 81| 94| 19| 16| 45| 66|
1448 +---+---+---+---+---+---+---+---+---+---+
1449 | 22| 91| 96| 93| 20| 69| 82| 67| 18| 15|
1450 +---+---+---+---+---+---+---+---+---+---+
1453 weakref_tests
= """\
1454 Generators are weakly referencable:
1460 >>> wr = weakref.ref(gen)
1463 >>> p = weakref.proxy(gen)
1465 Generator-iterators are weakly referencable as well:
1468 >>> wr = weakref.ref(gi)
1471 >>> p = weakref.proxy(gi)
1477 coroutine_tests
= """\
1478 Sending a value into a started generator:
1490 Sending a value into a new generator produces a TypeError:
1493 Traceback (most recent call last):
1495 TypeError: can't send non-None value to a just-started generator
1498 Yield by itself yields None:
1506 An obscene abuse of a yield expression within a generator expression:
1508 >>> list((yield 21) for i in range(4))
1509 [21, None, 21, None, 21, None, 21, None]
1511 And a more sane, but still weird usage:
1513 >>> def f(): list(i for i in [(yield 26)])
1518 A yield expression with augmented assignment.
1520 >>> def coroutine(seq):
1522 ... while count < 200:
1524 ... seq.append(count)
1526 >>> c = coroutine(seq)
1541 Check some syntax errors for yield expressions:
1543 >>> f=lambda: (yield 1),(yield 2)
1544 Traceback (most recent call last):
1546 SyntaxError: 'yield' outside function (<doctest test.test_generators.__test__.coroutine[21]>, line 1)
1548 >>> def f(): return lambda x=(yield): 1
1549 Traceback (most recent call last):
1551 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.coroutine[22]>, line 1)
1553 >>> def f(): x = yield = y
1554 Traceback (most recent call last):
1556 SyntaxError: assignment to yield expression not possible (<doctest test.test_generators.__test__.coroutine[23]>, line 1)
1558 >>> def f(): (yield bar) = y
1559 Traceback (most recent call last):
1561 SyntaxError: can't assign to yield expression (<doctest test.test_generators.__test__.coroutine[24]>, line 1)
1563 >>> def f(): (yield bar) += y
1564 Traceback (most recent call last):
1566 SyntaxError: augmented assignment to yield expression not possible (<doctest test.test_generators.__test__.coroutine[25]>, line 1)
1569 Now check some throw() conditions:
1575 ... except ValueError,v:
1576 ... print "caught ValueError (%s)" % (v),
1581 >>> g.throw(ValueError) # type only
1582 caught ValueError ()
1584 >>> g.throw(ValueError("xyz")) # value only
1585 caught ValueError (xyz)
1587 >>> g.throw(ValueError, ValueError(1)) # value+matching type
1588 caught ValueError (1)
1590 >>> g.throw(ValueError, TypeError(1)) # mismatched type, rewrapped
1591 caught ValueError (1)
1593 >>> g.throw(ValueError, ValueError(1), None) # explicit None traceback
1594 caught ValueError (1)
1596 >>> g.throw(ValueError(1), "foo") # bad args
1597 Traceback (most recent call last):
1599 TypeError: instance exception may not have a separate value
1601 >>> g.throw(ValueError, "foo", 23) # bad args
1602 Traceback (most recent call last):
1604 TypeError: throw() third argument must be a traceback object
1606 >>> def throw(g,exc):
1610 ... g.throw(*sys.exc_info())
1611 >>> throw(g,ValueError) # do it with traceback included
1612 caught ValueError ()
1617 >>> throw(g,TypeError) # terminate the generator
1618 Traceback (most recent call last):
1622 >>> print g.gi_frame
1626 Traceback (most recent call last):
1630 >>> g.throw(ValueError,6) # throw on closed generator
1631 Traceback (most recent call last):
1635 >>> f().throw(ValueError,7) # throw on just-opened generator
1636 Traceback (most recent call last):
1640 >>> f().throw("abc") # throw on just-opened generator
1641 Traceback (most recent call last):
1643 TypeError: exceptions must be classes, or instances, not str
1645 Now let's try closing a generator:
1649 ... except GeneratorExit:
1656 >>> g.close() # should be no-op now
1658 >>> f().close() # close on just-opened generator should be fine
1660 >>> def f(): yield # an even simpler generator
1661 >>> f().close() # close before opening
1664 >>> g.close() # close normally
1679 GeneratorExit is not caught by except Exception:
1683 ... except Exception: print 'except'
1684 ... finally: print 'finally'
1692 Now let's try some ill-behaved generators:
1696 ... except GeneratorExit:
1701 Traceback (most recent call last):
1703 RuntimeError: generator ignored GeneratorExit
1707 Our ill-behaved code should be invoked during GC:
1709 >>> import sys, StringIO
1710 >>> old, sys.stderr = sys.stderr, StringIO.StringIO()
1714 >>> sys.stderr.getvalue().startswith(
1715 ... "Exception RuntimeError: 'generator ignored GeneratorExit' in "
1718 >>> sys.stderr = old
1721 And errors thrown during closing should propagate:
1725 ... except GeneratorExit:
1726 ... raise TypeError("fie!")
1730 Traceback (most recent call last):
1735 Ensure that various yield expression constructs make their
1736 enclosing function a generator:
1738 >>> def f(): x += yield
1742 >>> def f(): x = yield
1746 >>> def f(): lambda x=(yield): 1
1750 >>> def f(): x=(i for i in (yield) if (yield))
1754 >>> def f(d): d[(yield "a")] = d[(yield "b")] = 27
1768 ... except StopIteration: pass
1774 refleaks_tests
= """
1775 Prior to adding cycle-GC support to itertools.tee, this code would leak
1776 references. We add it to the standard suite so the routine refleak-tests
1777 would trigger if it starts being uncleanable again.
1779 >>> import itertools
1782 ... def __iter__(self):
1785 ... return self.item
1787 ... head, tail = itertools.tee(g)
1792 Make sure to also test the involvement of the tee-internal teedataobject,
1793 which stores returned items.
1795 >>> item = it.next()
1799 This test leaked at one point due to generator finalization/destruction.
1800 It was copied from Lib/test/leakers/test_generator_cycle.py before the file
1813 This test isn't really generator related, but rather exception-in-cleanup
1814 related. The coroutine tests (above) just happen to cause an exception in
1815 the generator's __del__ (tp_del) method. We can also test for this
1816 explicitly, without generators. We do have to redirect stderr to avoid
1817 printing warnings and to doublecheck that we actually tested what we wanted
1820 >>> import sys, StringIO
1821 >>> old = sys.stderr
1823 ... sys.stderr = StringIO.StringIO()
1825 ... def __del__(self):
1826 ... raise RuntimeError
1830 ... err = sys.stderr.getvalue().strip()
1832 ... "Exception RuntimeError: RuntimeError() in <"
1834 ... err.endswith("> ignored")
1835 ... len(err.splitlines())
1837 ... sys.stderr = old
1844 These refleak tests should perhaps be in a testfile of their own,
1845 test_generators just happened to be the test that drew these out.
1849 __test__
= {"tut": tutorial_tests
,
1851 "email": email_tests
,
1853 "syntax": syntax_tests
,
1854 "conjoin": conjoin_tests
,
1855 "weakref": weakref_tests
,
1856 "coroutine": coroutine_tests
,
1857 "refleaks": refleaks_tests
,
1860 # Magic test name that regrtest.py invokes *after* importing this module.
1861 # This worms around a bootstrap problem.
1862 # Note that doctest and regrtest both look in sys.argv for a "-v" argument,
1863 # so this works as expected in both ways of running regrtest.
1864 def test_main(verbose
=None):
1865 from test
import test_support
, test_generators
1866 test_support
.run_doctest(test_generators
, verbose
)
1868 # This part isn't needed for regrtest, but for running the test directly.
1869 if __name__
== "__main__":