Wednesday, May 16, 2007

Enumerating Integers

My friend Dave B. came to me with a programming problem today. The end goal is to compute the minimum collection of pennies, nickels, dimes and quarters you need to make any amount under a dollar. This can be broken up into two major parts, the first of which is enumerating integer combinations. I will arrive at this algorithm in two steps. The first is something I've solved before and forgot about; the second step is a patching-up of the first which Dave helped me with.

When I visited my Grandmother growing up, I would sleep in a spare bedroom with many unfamiliar objects. The most captivating was this digital clock with a mechanical display instead of LEDs. As time passed, the numbers would flip over like a Rolodex to reveal the next one, finally looping back to 0. When the minutes position looped back to zero, the ten's (of minutes) position would flip over. If the ten's position flipped back to zero, then the hour position would flip over too.

Right vs. Left Directions in an Array.
When I write out an array, I do so like this:
array: [a,b,c,d]
index: 0 1 2 3

The first row shows the array contents itself and the second row shows the indexes used to access the array elements. The first element a is leftmost, and the last element d is rightmost, and I would say that b is to the left of c.

We can enumerate a 'permutation' of integers in this way. The idea is to have each combination of the integers 0..max in each element of the array. (This is not a true mathematical permutation because the collection of numbers we are selecting from has duplicates and is thus not a set.) Note that this will enumerate the indexes to access all elements of an N-dimensional array without needing N nested loops.

First, create an array ary with 3 elements. Then, starting at the rightmost index, increment the element at that index until it overflows (i.e. goes above the max value, 2). When it overflows, reset it to 0 (zero) and increment the element to the left of the current one until they stop overflowing. If you need to increment an element past the start of the array (less than index zero), then you are done enumerating. Ruby code implementing this algorithm follows:


ary = [0, 0, 0]
loop do
k = ary.length - 1
p ary
while (ary[k] += 1) == 2
ary[k] = 0
k -= 1
return if k < 0
end
end


We could easily generalize this to parameterize the number of integers and their min and max values:


def permute_integers(count, min, max)
ary = [min] * count
loop do
k = count - 1
yield ary
while (ary[k] += 1) >= max
ary[k] = min
return if (k -= 1) < 0
end
end
end


Where count is the number of integers in each list and min and max denote the open interval min <= n < max and n is the set of values each integer in the list can take. A simple test reveals:


irb(main):015:0> permute_integers(2, 1, 4) { |a| p a }
[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]
=> nil


Now that's all well and good if we're enumerating multi-dimensional array indexes. For coin counting, we really need a 'combination' because the order of the numbers doesn't matter. This requires a different updating strategy. On each iteration, find the rightmost array element that will not overflow if we increment it. Increment that element and copy its new value to the elements to its right, if any. Modifying permute_integers with this strategy gives:


def combine_integers(count, min, max)
ary = [min] * count
loop do
k = ary.length - 1
yield ary
while ary[k] >= max - 1
return if (k -= 1) < 0
end
v = ary[k] + 1
(k...count).each {|i| ary[i] = v }
end
end


To see that this works, let's take the above example and delete those integer collections that are mere reorderings of others:


[1, 1]
[1, 2]
[1, 3]
[2, 1] (same as [1, 2])
[2, 2]
[2, 3]
[3, 1] (same as [1, 3])
[3, 2] (same as [2, 3])
[3, 3]



Testing combine_integers with the same parameters as the permute_integers test, we get:


irb(main):013:0> combine_integers(2, 1, 4) { |a| p a }
[1, 1]
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 3]
=> nil


Which is exactly the list we created manually. After trying this with three integers, I feel assured that the algorithm works. I am not mathematician enough for a real proof, sorry.

Monday, May 14, 2007

Lua: Good or Evil?

I was just checking out Lua as I look for a language for scripting 3d applications. Lua is a neat little language that combines Algol family syntax with the Lisp idea of basic but powerful language constructs. Most exciting are functions and associative arrays. The functions act as closures and can be treated as first-class values. The associative arrays are true to their name, but with a twist in the implementation. Internally, they store values either as an array or a hash table depending on how you index the elements. PHP (associative) 'arrays' done right. I've heard Lua described as a 'fixed Javascript.' And it's speedy.

As I was going through the "Programming in Lua" book I was severely disappointed to learn that the language and relevant library functions assume 1-based indexing for arrays, strings and variadic function parameters. After more than 10 years of C, C++, Ruby and other 0-based indexing languages, that's just too much to swallow. It's a wonderful little language, but if it's going to make me throw out all my hard-earned 0-based indexing tricks and correctness reasoning skills, I won't have it.

The Lua wiki shows some controversy on the subject: http://lua-users.org/wiki/CountingFromOne but no serious moves to change anything. There was a good article by Edsger Dijkstra linked there, "Why numbering should start at zero."