Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 76 lines
 1
 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.

1 comment

Collin Stocks 12 years, 11 months ago  # | flag

What is the purpose of your program, before I vote on it?

Created by Don Sawatzky on Sun, 14 Dec 2008 (MIT)
Python recipes (4591)
Don Sawatzky's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks