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:
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.
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.
