Leif Ryge

[Python] changeWordSize

2011-07-18T18:31:21-07:00

Generator which transforms a sequence of n-bit "words" (0 <= i < 2**n) into a sequence of words of some other size. This works, but I feel like it could be made a lot clearer.

def changeWordSize ( words, inSize, outSize ):
    """
    >>> list( changeWordSize( [255, 18], 8, 1 ) )
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0]
    >>> list( changeWordSize( [255, 18], 8, 4 ) )
    [15, 15, 1, 2]
    >>> list( changeWordSize( [15, 15, 1, 2], 4, 8 ) )
    [255, 18]
    """
    assert inSize  > 0
    assert outSize > 0
    bits  = 0
    value = 0
    for word in words:
        assert type(word) in (int, long), "words must be int or long, got %s" % ( type( word ), )
        assert 0 <= word < 2 ** inSize  , "words must be in range 0 to 2**%s-1, got %s" % ( inSize, word )
        value  = value << inSize
        value += word
        bits  += inSize
        while outSize <= bits:
            bits    -= outSize
            newWord  = value >> bits
            value   -= newWord << bits
            yield newWord
    if bits and inSize < outSize:
        yield value << (outSize - bits)

[Python] On Count word occurrences in a string

2008-10-31T20:37:23-07:00

Here is another version which uses the handy itertools.groupby function.

from itertools import groupby
import doctest

def printWordFrequencies(text):
    """
    >>> printWordFrequencies("Ob la di ob la da")
    1 da
    1 di
    2 la
    2 ob"""
    for w, g in groupby(sorted(text.lower().split())):
        print "%s %s" % (len(list(g)), w)

doctest.testmod(verbose=True)

[Python] On Count word occurrences in a string

2008-10-31T19:58:08-07:00

This prints not only the count but also the locations of each word.

def mk_index(seq):
    """Index a sequence
    >>> sorted(mk_index("abcba").items())
    [('a', [0, 4]), ('b', [1, 3]), ('c', [2])]"""
    result={}
    for location, item in enumerate(seq):
        result.setdefault(item,[]).append(location)
    return result

def printWordFrequencyAndLocationReport(text):
    """Report count and locations of each word in text
    >>> printWordFrequencyAndLocationReport('Ob la di ob la da')
    ob occurred 2 times [0, 3]
    la occurred 2 times [1, 4]
    da occurred 1 time [5]
    di occurred 1 time [2]"""
    for word, locs in sorted(mk_index(text.lower().split()).items(),
                             key=lambda (w,l): len(l), reverse=True):
        print "%s occurred %s time%s %s" % (word, len(locs),
                                            ('','s')[len(locs)>1], locs)

import doctest
doctest.testmod(verbose=True)

[Python] On Computing permutations with a recursive generator expression

2008-10-31T06:55:07-07:00

Answering my own question: the caveat to idiom_B is that it isn't short-circuiting. So, if instead of z and y we had z() and y() then evaluating the expression causes BOTH functions to be called (regardless of the value of x) in idiom_B, while in A and C only the desired function is called.

[Python] On Computing permutations with a recursive generator expression

2008-10-30T20:23:38-07:00

Thanks! I was actually unaware that booleans could be used as getitem keys, which is a very useful trick. I wonder why I've seen this ugly idiom A in wide use instead of the much more elegant B:

idiom_A = lambda x,y,z: (x and [y] or [z])[0]
idiom_B = lambda x,y,z: (z, y)[x]
idiom_C = lambda x,y,z: y if x else z # introduced in Python 2.5

[Python] On Permutation of values

2008-10-22T04:55:08-07:00

[edit: redacted, sorry]

[Python] Computing permutations with a recursive generator expression

2008-10-22T04:16:41-07:00

I suspect there is a better way to deal with the end of the sequence.

#!/usr/bin/python2.5
def permute(li):
    """Generate all permutations of a sequence
    >>> for i in permute([1,2,3]): print i
    (1, 2, 3)
    (1, 3, 2)
    (2, 1, 3)
    (2, 3, 1)
    (3, 1, 2)
    (3, 2, 1)"""
    return ((i,)+j for i in li for j in (permute([k for k in li if k is not i])
                                         if len(li) > 1 else [()] ) )

import doctest
doctest.testmod(verbose=True)