P is for Practical PerlMonks

### Re: Hamming Sequences and Lazy Lists

by kvale (Monsignor)
 on Mar 17, 2005 at 08:56 UTC ( #440306=note: print w/replies, xml ) Need Help??

in reply to Hamming Sequences and Lazy Lists

Here is a solution that is not lazy and not quite as efficient as the Haskell version, but is simple:
```use Algorithm::Loops qw(NestedLoops);
use List::Util qw(reduce);

my @factors = (2,3,5);  # Assmue increasing sequence
my \$seq_len = 10;
my \$depth = int( \$seq_len ** (1/@factors)) + 1;

my @seq;
my @list= NestedLoops(
[  ( [ 0..\$depth ] ) x @factors  ],
sub { push @seq, reduce {\$a * \$b}
map {\$factors[\$_]**\$_[\$_]} 0..\$#_;},
);

my @sorted = sort {\$a <=> \$b} @seq;
print "\$sorted[\$_] " foreach 0..\$seq_len-1;
Update: Improved the depth bound.

-Mark

Replies are listed 'Best First'.
Re^2: Hamming Sequences and Lazy Lists
by Limbic~Region (Chancellor) on Mar 17, 2005 at 16:48 UTC
kvale,
I don't think this is right. Shouldn't the result include all factors of all 3 lists merged minus duplicates? If you change \$seq_len = 23 for instance, why is 16 for instance missing from the results? See Re: Hamming Sequences and Lazy Lists for my understanding and implementation of the problem.

Cheers - L~R

Given the OP's reference to the factors of a composite number thread, I interpreted 'use an unlimited number of times" to mean create numbers of the form
```2**\$i * 3**\$j * 5**\$k
with \$i, \$j, and \$k as integers >= 0. The program I wrote generalizes this by handling an arbitrary number of arbitrary factors.

I don't know what you mean by 'factors of 3 lists', but if I guess that each list is a multiple of each factor, then I think that must not be right. The example given by the OP had 1 as the first member, but 1 is not any multiple 2, 3, or 5.

That said, there is an error my program :) 16 should be in the list even in my understanding of the problem. The mistake with is that the bound on the \$depth I set was too low. In the harsh light of the morning, a safe bound is

```my \$depth = \$seq_len;
But I am sure this bound can be made tighter, right after I have some tea :)

-Mark

kvale,
I understand the need for caffeine. I plan on cleaning my code up too. Here is a visual representation of my understanding of the Hamming sequence.
```2 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, ...
3 = 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...
5 = 5, 10, 15, 20, 25, 30, ...

H = 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 16, 18, 20, 21, 22, 24, 25, 26
+, 27, 28, 30, ...

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.

Create A New User
Node Status?
node history
Node Type: note [id://440306]
help
Chatterbox?
 choroba still has one more. [Corion]: I have Thursday and Friday off, so then I might get to converting the rough outlines to more articles ;) [Corion]: But currently, most of the modules are web-related and I don't like to publish two web articles in a row [Corion]: Maybe I should do the Filter::Simple release on the next weeked - this would give me one more article to milk from this theme

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (8)
As of 2017-04-24 08:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I'm a fool:

Results (437 votes). Check out past polls.