Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: Generating powerset with progressive ordering

by tall_man (Parson)
on Feb 25, 2005 at 18:47 UTC ( #434602=note: print w/ replies, xml ) Need Help??


in reply to Generating powerset with progressive ordering

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.

#! /usr/bin/perl use strict; use Math::Pari qw(:int factorint divisors); for (@ARGV) { my $N = $_; my $a = factorint($N); my $div = divisors($a); print "sorted list of divisors of $N is ",$div,"\n"; }

For 12345, this prints:

perl ddd.pl 12345 sorted list of divisors of 12345 is [1,3,5,15,823,2469,4115,12345]

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:

module Powerset where {- Expand muliplies of two list of numbers. For example: mult_expand [1, 2, 4] [1, 5] Produces: [[1,5],[2,10],[4,20]] -} mult_expand p [] = p:[] mult_expand p lst = map (\x -> map (*x) lst) p {- expand the powers of x from 0 to exp -} pows x exp = map (\e -> x^e) [0..exp] {- expand the powers the first item in a pair from 0 to the second item in the pair. -} powerlst p = pows (fst p) (snd p) {- One stage of a merge sort -} merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys {- Do multiple merges to get an ordered list. -} bigmerge lsts = foldl merge [] lsts {- The complete power set of a list of factor/exponent pairs. For exa +mple: powerset [(2,3),(5,1)] Produces: [1,2,4,5,8,10,20,40] -} powerset [] = [] powerset (x:xs) = bigmerge (mult_expand (powerlst x) (powerset xs)) {- Helper function for factor_sqrt. Finds the last list value less than or equal to the given limit. -} fsqrt lim lastgood [] = lastgood fsqrt lim lastgood (x:xs) = if (x > lim) then lastgood else fsqrt lim x xs {- Find the last divisor less than the square root, given the number and its factors -} factor_sqrt n factors = fsqrt (sqrt n) 0 (powerset factors)

For example, under Hugs:

Prelude> :l Powerset.hs Powerset> factor_sqrt 24777695232 [(2,13),(3,8),(461,1)] 149364.0


Comment on Re: Generating powerset with progressive ordering
Select or Download Code
Re^2: Generating powerset with progressive ordering
by Limbic~Region (Chancellor) on Feb 25, 2005 at 19:16 UTC
    tall_man,
    Regarding using Math::Pari's divisors. This is really cool and I need to learn more about this module. It is however a violation of the original question as stated. Only the prime factorization is to be known initially. I will look at the second part of your response in bit.

    Cheers - L~R

      I object to calling the use of divisors a "violation" of the original question. Given the prime factorization, it is a simple matter to multiply out all the possible combinations, giving the list of divisors. Math::Pari's divisor function just saves the work of doing the multiplications and sorting the results.
        tall_man,
        Given the downvotes - you aren't the only one who feels this way. I still like your solution for brevity, efficiency, and elegance even if it isn't the fastest. I really do need to learn more about Math::Pari.

        Cheers - L~R

Re^2: Generating powerset with progressive ordering
by Limbic~Region (Chancellor) on Feb 28, 2005 at 19:55 UTC
    tall_man,
    Cool, a Haskell solution - you should be on the Pugs team ;-)

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://434602]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (7)
As of 2014-12-26 08:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (169 votes), past polls