Quick Tip #4: The Hamming Sequence and hyper-operators

The Hamming Sequence shows up in programming exercises. It’s the sequence of numbers that have only 2, 3, or 5 as divisors. The trick is to generate them in ascending order. Dijkstra figured it out, but he cheated a bit by restraining his problem to the first 1,000 values. Some people have a pre-occupation with programs that finish.

Dijkstra figured this out. Remember the elements in the list. Keep a set of indices to remember which elements in the list already have their multiples in the list. To get the next element in the sequence, try the next multiple for each factor. Take the least one and add it to the list. Increment the indices for the factors that produced a value less than or equal to the value just added. That’s the next index to try for that factor.

In Perl 6 (or many other langauges), a direct translation of that might look like this:

sub get_sequence { my $seq := 1, { dijkstra() } ... *  }

sub MAIN ( $number = 30 ) {
	my $seq = get_sequence;

	say $seq[^$number];
	}

sub dijkstra {
	state @h = <1>;
	state ( $i, $j, $k ) = < 0 0 0 >;

	@h.push( min( 2*@h[$i], 3*@h[$j], 5*@h[$k] ) );

	$i++ if 2*@h[$i] <= @h[*-1];
	$j++ if 3*@h[$j] <= @h[*-1];
	$k++ if 5*@h[$k] <= @h[*-1];

	return @h[*-1];
	}

I wrote about lazy sequences in User-defined infinite sequences and the MAIN in Perl 6 modulinos are even easier. The *-1 in the @h subscript gets me the last element. Perl 6 doesn't count backward, but a * (the Whatever thingy) in the subscript gets the number of elements in the array. From that I subtract 1 to get the last index.

But, I can do better. First, that example hard-coded the 2, 3, and 5. There are other "smooth numbers" that factor only into powers of small prime numbers.

So, I'll put the factors into their own array. Later I can convert that to a configurable parameter. I might want different factors, or a different number of factors.

sub dijkstra {
	state @h       = <1>;
	state @factors = < 2 3 5 >;
	state @indices = < 0 > xx @factors;

	@h.push( min( @h[ @indices ] <<*>> @factors ) );

	...;

	return @h;
	}

So, I'll create an array of indices that has the same length of factors. The list replication, xx does that for me. The array @factors, in numeric context, is the number of elements.

Then I use one of my favorite features of Perl, the hyper-operator. Let me break out that bit from the code:

@h[ @indices ] <<*>> @factors

In the first example, I needed to multiply individual elements in @h with a list of factors (even though I hard-coded them). That's what the hyper-operators do. It applies the operator between the angle brackets to corresponding elements of each list. In this case, it multiplies the first elements of each list, then the second, and so on. The grand result of is the list of results. I can put just about any operator in there that I like (and in a moment I'll do something fancy with that).

In this case, I've used @indices to create an array slice of the elements in @h that still need a multiple. I hyper-multiply that with
@factors. It's the same thing as this line from the first example:

( 2*@h[$i], 3*@h[$j], 5*@h[$k] )

But, this stuff won't work with the next bit because I got rid of the $i, $j, and $k variables. Those values are now in the @indices. so I've used the ... stub operator (or, the "yada yada"). That compiles, but Perl 6 dies when it executes it. I use it as a placeholder for work I still need to do.

Let's build up the next part. I need to increment the indices for the factors that produce sequence elements that are the same or less than the last value I stored in @h. In the first example I had three lines of code with repeated structure.

First, I need to figure out which indices I want to increment. Those are the ones where element in @h at that index is less than or equal to the last element in @h. Remember, some multiples will overlap when they have common factors. The number 10 is in the sequence because 5 is in the sequence and 5*2 is 10. But, it's also in the sequence because 2 is in the sequence and 2*5 is 10.

I can use the same code I just used to get the products:

( @h[ @indices ] <<*>> @factors )

Now, I need to know which of those products are less than the last element of @h. I can use the hyper-operator again, but this time with
the <= comparator:

( @h[ @indices ] «*» @factors ) «<=» @h[*-1]

But, I had to do something else here. When I put the <= between the ASCII angle brackets, all sorts of parser confusion ensues. But, Perl 6 has a way around this by using fancy Unicode characters. The « and » characters do the same job, and since they aren't the ASCII version, the parser doesn't have a chance to confuse which angle brackets belong to what. Perl 6 calls the ASCII versions "Texas-style". For the non-Americans, Texas is a state in the U.S. that thinks they are the biggest. They're okay. They invented fajitas, Tex-Mex, and Franklin BBQ, so they can say that. The ASCII quotes are bigger, so Larry calls them "Texas". You may know about "Jersey barriers" used to divide roads, but there are larger versions called "Texas barriers" as well as the largest version called Alaska Barriers. Don't tell Damian Conway or he might come up with even larger quoting mechanisms! But back to Perl 6.

The result of those two hyper-operators is a list of True and False values. The position of the Boolean value indicates whether I should increment the index in the same position. Now that I'm that far, I can use a third hyper, this time with binary addition, to numerically add that list of Boolean values to @indices:

@indices «+=» ( ( @h[ @indices ] «*» @factors ) «<=» @h[*-1] )

Putting that together, I have something with no if statements:

sub dijkstra () {
	state @h       = < 1 >;   # and so could this!
	state @factors = <2 3 5>; # this could be a parameter
	state @indices = < 0 > xx @factors;

	# add the next least multiple. This is the next number
	# in the sequence.
	@h.push( min( @h[ @indices ] «*» @factors ) );

	# Adjust the indices for the factor that were in the next number
	# more than one of these can be true!
	# For instance, 10 is both 5 * 2 and 2 * 5.
	@indices «+=» ( ( @h[ @indices ] «*» @factors ) «<=» @h[*-1] );

	@h[*-1];
	}

This generates the next value in the Hamming sequence. But, I'm not done yet. The @h array holds the entire sequence even after I don't need some of the elements. I should get rid of those. Once all the indices are at least 1, I don't need the zeroth element anymore. I should get rid of it:

sub dijkstra () {
	state @h       = < 1 >;   # and so could this!
	state @factors = <2 3 5>; # this could be a parameter
	state @indices = < 0 > xx @factors;

	# add the next least multiple. This is the next number
	# in the sequence.
	@h.push( min( @h[ @indices ] «*» @factors ) );

	# Adjust the indices for the factor that were in the next number
	# more than one of these can be true!
	# For instance, 10 is both 5 * 2 and 2 * 5.
	@indices «+=» ( ( @h[ @indices ] «*» @factors ) «<=» @h[*-1] );

	# remove elements we don't need any more and adjust indices
	# the least element should be 1. If the index is 1, the number
	# in @h[0] already has multiples of @factors in the sequence
	if all( @indices ) > 0 {
		@h.shift;
		@indices>>--;
		}

	@h[*-1];
	}

In the last bit of code, I just the all Junction to check that every index is greater than 0. If so, I take the first element off @h. But, when I do that, I need to adjust all of the indices down one. The hyper-operators work for unary operators (such as the auto-decrement --). This time there's one set of quotey things, with the alligator mouth toward the list thingy.

Leave a Reply

Your email address will not be published. Required fields are marked *