[Resolved] Generalized Hamming numbers in Python

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

Moderators: phlip, Moderators General, Prelates

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

[Resolved] Generalized Hamming numbers in Python

Postby LucasBrown » Sat May 07, 2016 8:04 pm UTC

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, groupby
from heapq import merge
def 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([1], 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([1], 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.

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

Re: Generalized Hamming numbers in Python

Postby Xanthir » Sun May 08, 2016 5:38 am UTC

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)))

User avatar
PM 2Ring
Posts: 3617
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Generalized Hamming numbers in Python

Postby PM 2Ring » Sun May 08, 2016 8:34 am UTC

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, islice
from heapq import merge

def 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([1], merge(m2, m3, m5))))
    return result

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):
        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([1], merge(*ms))))
    return t[-1]

# Test
print(all(== 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([1], merge(*ms))))
    return t[-1]
Last edited by PM 2Ring on Mon May 09, 2016 2:44 pm UTC, edited 4 times in total.

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

Re: [Resolved] Generalized Hamming numbers in Python

Postby LucasBrown » Sun May 08, 2016 7:51 pm UTC

Thanks; that was enlightening.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests