Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re: Hamming Sequences and Lazy Lists

by Limbic~Region (Chancellor)
on Mar 17, 2005 at 16:44 UTC ( #440431=note: print w/ replies, xml ) Need Help??


in reply to Hamming Sequences and Lazy Lists

tall_man,
The only thing that is recursive is merge() which could also be iterative. I believe it does what you want.

#!/usr/bin/perl use strict; use warnings; use constant HEAD => 0; use constant TAIL => -1; # Usage my $next = genHam( take => #, list => [<factors>] ); # If take is not specified, it assumes infinity my $next = genHam( take => 23, list => [2, 3, 5] ); while ( my $n = $next->() ) { print "$n\n"; } sub genHam { die "Incorrect number of arguments" if @_ % 2; my %arg = @_; return () if ! exists $arg{list} || ref $arg{list} ne 'ARRAY'; $arg{take} ||= -1; my $n = 0; my (@pool, @stream); push @stream, [] for 0 .. $#{ $arg{list} }; $stream[TAIL] = [ $arg{list}->[TAIL] ]; return sub { return () if ! $arg{take}--; # Return obligatory 1 return ++$n if ! $n; # No need to generate as we already have some in the pool return shift @pool if @pool; # Increase highest factor $stream[TAIL] = [ $arg{list}->[TAIL] * $n ]; ++$n; # Generate streams of multiples >= highest factor for my $i ( 0 .. $#stream - 1 ) { # Start with empty stream $stream[ $i ] = []; my $multiple = $arg{list}->[ $i ]; # Determine what multiple each factor should start at my $start = $n > 2 ? ($arg{list}->[TAIL] * ($n - 2)) / $mu +ltiple + 1 : 1; # Add multiples to the stream less than or equal to the hi +ghest factor for ( $start .. $stream[TAIL]->[HEAD] / $multiple ) { push @{ $stream[ $i ] }, $multiple * $_; } } # Merge streams into new pool @pool = @{ $stream[HEAD] }; for ( 1 .. $#stream ) { @pool = merge(\@pool, $stream[ $_ ]); } # Return first member of pool return shift @pool; } } sub merge { my ($s1, $s2) = @_; return @$s2 if ! @$s1; return @$s1 if ! @$s2; return shift @$s1, merge( @_ ) if $s1->[HEAD] < $s2->[HEAD]; return shift @$s2, merge( @_ ) if $s1->[HEAD] > $s2->[HEAD]; shift @$s1; return shift @$s2, merge( @_ ); }

Cheers - L~R

Update: This is wrong. I was so focused on lazy evaluation that I misunderstood "how do you generate the series of numbers composed of a given list of prime factors, where each can be used an unlimited number of times?" To me, that meant any positive multiple of any factor was valid.


Comment on Re: Hamming Sequences and Lazy Lists
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (8)
As of 2014-10-02 08:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (52 votes), past polls