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.