## [Resolved] Generalized Hamming numbers in Python

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

### [Resolved] Generalized Hamming numbers in Python

I found an elegant and efficient Hamming number generator in Python, which I have modified a bit to fit my own personal idiom:

Code: Select all

`from itertools import tee, chain, groupbyfrom heapq import mergedef hamming0():    def deferred_output(): yield from output    p2, p3, p5, result = tee(deferred_output(), 4)    m2, m3, m5 = (2*x for x in p2), (3*x for x in p3), (5*x for x in p5)    output = (k for (k,_) in groupby(chain(, merge(m2, m3, m5))))    return result`
The only downside is that it is locked in to producing only numbers of the form 2x×3y×5z, and for various purposes I would like a similarly elegant and efficient in-order generator for Hamming numbers from an arbitrary set of primes. Unfortunately, the obvious modification fails: rewriting the code as

Code: Select all

`def hamming1(ps=(2,3,5)):    def deferred_output(): yield from output    t = tee(deferred_output(), len(ps)+1)    ms = [(m*x for x in t[i]) for (i,m) in enumerate(ps)]    output = (k for (k,_) in groupby(chain(, merge(*ms))))    return t[-1]`
produces an iterator that only yields the powers of 5 (or whatever the last element of the argument is).

1. Why does this fail?

2. How can it be modified to produce Hamming numbers from an arbitrary set of primes?
Last edited by LucasBrown on Sun May 08, 2016 7:51 pm UTC, edited 1 time in total. https://pypi.python.org/pypi/labmath
3239×21412529+1 is prime!

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

### Re: Generalized Hamming numbers in Python

Common issue in Javascript, and why the new for-of loop has some non-obvious semantic details when you use a let in its head.

Your problem is that the i variable is created once, at the beginning of the outer list comprehension, and each of the generator expressions closes over it. It gets updated multiple times while constructing the list of generators, and when they're finally called, since all of them are referring to the same variable, they all use the last value that variable was set to.

To fix it, you need to indirect thru a function - make a function that takes m and t[i] as arguments, and returns a generator like what you have; call the function in the list comprehension instead. Then each generator expression will have closed over the *function-local* variables, which only ever have a single value, and you should get the result you expect.

(I haven't tested this, but it's the way you solve this in old-JS when setting up multiple async callbacks that pay attention to the looping variable.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: Generalized Hamming numbers in Python

What Xanthir said, although you really only need to worry about m. Here's my version. It creates the generator expressions using a function multiples that takes i and m as args. It would work if you only pass m as an arg, but I think it improves readability to pass them both.

My code doesn't use yield from because I'm running an ancient version of Python. This code should perform correctly on Python 2 or 3, although on Python 2 it'd be slightly better to replace range with xrange and zip with izip.

Code: Select all

`from itertools import tee, chain, groupby, islicefrom heapq import mergedef hamming0():    def deferred_output():        for u in output: yield u    p2, p3, p5, result = tee(deferred_output(), 4)    m2, m3, m5 = (2*x for x in p2), (3*x for x in p3), (5*x for x in p5)    output = (k for k,_ in groupby(chain(, merge(m2, m3, m5))))    return resultdef hamming1(ps=(2,3,5)):    def deferred_output():        for u in output: yield u    t = tee(deferred_output(), len(ps)+1)    def multiples(i, m):        return (m*x for x in t[i])    ms = [multiples(i, m) for i,m in enumerate(ps)]    output = (k for k,_ in groupby(chain(, merge(*ms))))    return t[-1]# Testprint(all(u == v for _,u,v in zip(range(999), hamming0(), hamming1())))print(list(islice(hamming1((3,5,7)), 20))) `
Output

Code: Select all

`True[1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, 81, 105, 125, 135, 147, 175]`

FWIW, you could implement multiples as a lambda,

Code: Select all

`ms = [(lambda m=m: (m*x for x in t[i]))() for i,m in enumerate(ps)]`

but that's far less readable, IMHO. Also, it's a little less efficient since the lambda itself is re-defined on every iteration of the enumeration.

Actually, it's probably more Pythonic to implement multiples as a simple generator function:

Code: Select all

`def hamming1(ps=(2,3,5)):    def deferred_output():        for u in output: yield u            t = tee(deferred_output(), len(ps)+1)    def multiples(i, m):        for x in t[i]:            yield m * x    ms = [multiples(i, m) for i,m in enumerate(ps)]    output = (k for k,_ in groupby(chain(, merge(*ms))))    return t[-1]`
Last edited by PM 2Ring on Mon May 09, 2016 2:44 pm UTC, edited 4 times in total.

LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

### Re: [Resolved] Generalized Hamming numbers in Python

Thanks; that was enlightening. https://pypi.python.org/pypi/labmath
3239×21412529+1 is prime!

Return to “Coding”

### Who is online

Users browsing this forum: No registered users and 9 guests