excellent - thanks in the meantime I managed to write something myself which a) works b) looks reasonably elegant and pythonic but c) is recursive d) requires a mainroutine and co-routine
I have a feeling if I analysed it it would prove to be relatively inefficient as I'm sure it creates a lot of temporary objects (partial lists) So I will gratefully try your version - and for interest's sake post mine at some point (its on other computer) for comment. Phil "Tim Peters" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > [Philp Smith] >> Does anyone have suggested code for a compact, efficient, elegant, most >> of >> all pythonic routine to produce a list of all the proper divisors of an >> integer (given a list of prime factors/powers) > > If the canonical factorization of N is the product of p_i**e_i, the > number of divisors is the product of e_i+1. This can be > astronomically large, so it's important to minimize the number of > multiplications performed, and to write a generator to produce the > divisors (it may, e.g., be impossible to materialize a list of all of > them). > > This one's easy and efficient: > > def gen_divisors(prime_list): > elts = sorted(set(prime_list)) > numelts = len(elts) > > # Split on the number of copies of elts[i]. > def gen_inner(i): > if i >= numelts: > yield 1 > return > thiselt = elts[i] > thismax = prime_list.count(thiselt) > > # powers <- [thiselt**i for i in range(thismax+1)], > # but using only thismax multiplications. > powers = [1] > for j in xrange(thismax): > powers.append(powers[-1] * thiselt) > > for d in gen_inner(i+1): > for prime_power in powers: > yield prime_power * d > > for d in gen_inner(0): > yield d > > For example, do: > > for d in gen_divisors([2, 3, 2, 3, 2, 3, 5, 2, 3]): > print d > > You're on your own for the "proper" business; try not to use more than > one line to do it <wink>. > > I find recursion clearest here. An iterative version is easy enough > to do by incrementing from 0 thru product(e_i) (and just skipping the > endpoints if you really want "proper") in a mixed-radix system defined > by the e_i. Exercise for the reader. > > Harder: generate divisors in increasing order. -- http://mail.python.org/mailman/listinfo/python-list
