Perl Monk, Perl Meditation 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 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 ) {
\$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
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;

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

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 contemplating the Monastery: (13)
As of 2016-05-31 15:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What font do you use for programming?

Results (383 votes). Check out past polls.