This procedure was proposed as a challenge to Python and other languages as the most concise coding. See Icon programming on the web. This is a lazy, recursive generator. It can be implemented several ways in Python with lists, iteration, and recursion. However, the lists increase in size exponentially with each iteration and recursion plus they are saved in every recursion. This recipe develops a lazy generator function.
Download
Copy to clipboard1 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #>>>>>>>>>> Icon example of recursive generator >>>>>>>>>
##procedure star(chars)
## suspend "" | (star(chars) || !chars)
##end
##
class bang(object):
""" a generator with saved state that can be reset """
def __init__(self, arg):
self.arg = arg
self.reset()
def __iter__(self):
for item in self.iterable:
yield item
def next(self):
return self.iterable.next()
def reset(self):
if hasattr(self.arg, '__iter__') and \
hasattr(self.arg, 'next') :
self.iterable = self.arg
elif hasattr(self.arg, '__getitem__'):
if self.arg:
self.iterable = iter(self.arg)
else: self.iterable = iter([""])
else:
self.iterable = iter([self.arg])
def __repr__(self):
return repr(self.arg)
def alternation( *items ):
"""Lazy evaluation that flattens input items """
for alt_item in items:
if hasattr(alt_item, '__iter__'):
#flatten generator item
for item in alt_item:
yield item
else:
yield alt_item
def concatenate(g1, g2):
"""Lazy evaluation concatenation """
#list, tuple, and string iterators are not used implicitly
#Not generalized for sequences other than strings
if hasattr(g1, '__iter__') and hasattr(g2, '__iter__'):
#concatenations of left items to right items
#map(operator.plus, leftseq, rightseq)
for x in g1:
g2.reset()
for y in g2:
yield x + y
elif hasattr(g1, '__iter__') :
#concatenations of left items to right sequence
#map(operator.plus, [leftseq]*len(rightseq), rightseq)
for x in g1:
yield x + g2
elif hasattr(g2, '__iter__') :
#concatenations of left sequence to right items
#map(operator.plus, leftseq, [rightseq]*len(leftseq))
for x in g2:
yield g1 + x
else:
#string concatenation like Python
yield g1 + g2
def star(chars):
""" Recursive, infinite generator for all permutations
of a string taken 1 to N characters at time """
for item in alternation("", concatenate(star(chars), bang(chars))):
yield item
#star test >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
chars = 'abc'
limit = 3 # Limit infinite recursion
for n, x in enumerate(star(chars)):
if len(x) > limit: break
print n+1, repr(x)
|
In Python terms, procedure star is a lazy, generator function that produces an infinite sequence of permutations of the argument's characters taken 0 or more at a time. The Python version is almost as concise, but only when the operators of the Icon version are implemented in Python. The ! operator implemented as the bang generator function is similar to Python's iter function. However, it must be implemented as a class that produces a resettable generator function. Resetting the bang generator is sometimes necessary; see its use in the concatenate function. The | operator is implemented as the alternation generator function. It is similar to itertools' chain function except it allows non-iterable as well as iterable arguments. The || operator is implemented as the concatenate generator function. It allows four possibilities of sequence and iterable objects as arguments. One possibility is similar to Python's sequence concatenation. These functions have not been verified for other than string sequences.
What is the purpose of your program, before I vote on it?