Don't ask to ask, just ask | |
PerlMonks |
Re: Generating powerset with progressive orderingby tall_man (Parson) |
on Feb 25, 2005 at 18:47 UTC ( [id://434602]=note: print w/replies, xml ) | Need Help?? |
I'd like to point out that in your solution you are already using Math::Pari for "factorint", so you could also use "divisors" to get the complete powerset in sorted order.
Update: adding code at Limbic~Region's request.
For 12345, this prints:
However, I see you are looking for a lazy evaluation method that will produce the whole list in sorted order, one at at time. I saw an example once in Haskell of this sort of thing. Suppose N = (p1^a1)*(p2^a2)*...(pr^ar) for p1..pr primes in sorted order. Form a1+1 lists: the first where p1 is not a factor, the second where p1 is a factor only once, ... up to the last list where p1 is a factor a1 times. Merge-sort these lists, in each case taking the lowest item available. That is your answer. These lists can be created recursively, by taking the next highest factor to all possible powers and merging in the same way. Update: I have written some Haskell code to do the recursive ennumeration of the factor list. Since Haskell does lazy evaluation, this code should compute the "factor square root" without multiplying out all the factors:
For example, under Hugs:
In Section
Seekers of Perl Wisdom
|
|