Counter Class -- Bag/Multiset

[pataphor]

On Thu, 22 Jan 2009 10:11:37 -0800 (PST)
Raymond Hettinger <python at rcn.com> wrote:

> The collections module in Python 2.7 and Python 3.1 has gotten a new
> Counter class that works like bags and multisets in other languages.

I like that! Now that we have a multiset or Counter I think a
redefinition of itertools.permutations is in order.

For example something like this:

def genperm(D, R = []):
    #generate the permutations of a multiset
    if not max(D.values()):
        yield tuple(R)
    else:
        for k,v in sorted(D.items()):
            if v: 
                D[k] -= 1
                for g in genperm(D,R+[k]): 
                    yield g
                D[k] += 1                

def perm(seq):
    D = {}
    for x in seq:
        D[x] = D.get(x,0)+1
    for X in genperm(D):
        yield X
    
def test():
    for i,x in enumerate(perm('aabbcc')):
        print i,x
    print len(set(perm('aabbcc')))
    
if __name__ == '__main__':
    test()

The dictionary I'm using here could be seamlessly replaced by your
Counter class.

By the way, I like your itertools recipes a lot, but I miss something
that repeats elements n times, an xcycle or ncycle or whatever, like I
used in this (older code, sorry for the name overlap):

def repeat(x,n = 0):
    i = 0
    while i < n :
        yield x
        i += 1

def xcycle(seq,n):
    while 1:
        for x in seq:
            for y in repeat(x,n):
                yield y    

def counter(symbols,width):
    base = len(symbols)
    R = []
    k = width
    while k:
        k -= 1
        R.append(xcycle(symbols,base**k))
    nc = base**width
    while nc:
        yield list(x.next() for x in R)
        nc -=1
        
def test():
    symbols = '01'
    width = 4
    for state in counter(symbols,width):
        print state

if __name__=='__main__':
    test()

I think such a thing could be handy for generating more kinds of
periodic sequences. By the way, itertools is starting to feel like it's
becoming some sort of alternate programming design all by itself. I
wonder when it is going to break loose from python! I like that
way of thinking a lot, thanks.

P.