Re: Hamming Sequences and Lazy Lists

Lazy, fast, and I think it's correct.

use strict; 
use warnings;

sub lazy_ham {
    my ($how_many) = @_;
    my @output_stream = (1);
    my @streams = map {
    my $base = $_;        # All your base are belong to us
    my $index = 0;
    sub {
        if (@_) { 
        return $base * $output_stream[$index];
        } else {
        return $base * $output_stream[$index++];
        }
    }
    } (2, 3, 5);
    for (1..$how_many) {
    # Find the lowest next item in the available streams
    my ($lowest) = sort {$a <=> $b} map {$_->('peek')} @streams;
    $_->('peek') == $lowest and $_->() for @streams;
    push(@output_stream, $lowest);
    }
    shift @output_stream; # Get rid of the seed 1
    @output_stream;
}

print join(', ', lazy_ham(1000)), "\n";
[download]

2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 4
+0, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125
+, 128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 25
+0, 256, 270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432, 450, 4
+80, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675, 720, 729, 750, 
+768, 800, 810, 864, 900, 960, 972, 1000, 1024, 1080, 1125, 1152, 1200
+, 1215, 1250, 1280, 1296, 1350, 1440, 1458, 1500, 1536, 1600, 1620, 1
+728, 1800, 1875,...
[download]

Caution: Contents may have been coded under pressure.

Comment on Re: Hamming Sequences and Lazy Lists Select or Download Code

Replies are listed 'Best First'.
Re^2: Hamming Sequences and Lazy Lists by tall_man (Parson) on Mar 17, 2005 at 18:25 UTC
The number 1 = 2*0 3*0 5**0, so it is a legitimate part of the series, not just a seed to be stripped off. It is part of the answer produced by the Haskell genHam above. Otherwise, your generator looks great and the output checks with the Haskell one.	[reply]
Re^3: Hamming Sequences and Lazy Lists by Roy Johnson (Monsignor) on Mar 17, 2005 at 18:40 UTC
Ok, well here it is, corrected for that, and without using coderefs for streams. I realized there really wasn't much point to that. All I really need to know is what my multiplier is, and which element of the output stream I'm looking at. `use strict; use warnings; sub lazy_ham { my ($how_many) = @_; my @output_stream = (1); my @streams = map [$_,0], (2, 3, 5); for (@output_stream+1..$how_many) { # Find the lowest next item in the available streams my @peeks = map {$output_stream[$_->[1]] * $_->[0]} @streams; my ($lowest) = sort {$a <=> $b} @peeks; $peeks[$_] == $lowest and $streams[$_][1]++ for 0..$#streams; push(@output_stream, $lowest); } @output_stream; } print join(', ', lazy_ham(80)), "\n";` [download] Caution: Contents may have been coded under pressure.	[reply] [d/l]
Re^2: Hamming Sequences and Lazy Lists by Limbic~Region (Chancellor) on Mar 17, 2005 at 18:03 UTC
Roy Johnson, Shouldn't 14 be in the results since it is a multiple of 2? Cheers - L~R	[reply]
Re^3: Hamming Sequences and Lazy Lists by Roy Johnson (Monsignor) on Mar 17, 2005 at 18:05 UTC
No, my understanding is that we only want numbers that factor as 2^X * 3^Y * 5^Z. Caution: Contents may have been coded under pressure.	[reply]
Re^4: Hamming Sequences and Lazy Lists by Limbic~Region (Chancellor) on Mar 17, 2005 at 18:23 UTC
Roy Johnson, You are correct, I am 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. Cheers - L~R	[reply]


Don't ask to ask, just ask
	PerlMonks