ruby - 如何遍历可能的整数数组，例如从 [1,1,1,1] 到 [1,1,1,2]，...最后到 [6,6,6,6]？

Question

有时我需要一种方法来做到这一点，想知道这是否是一个常见的问题或方法并且有一个名称:

比如，我们要遍历所有 4 个骰子的情况，或者遍历所有 20 个插槽的情况，每个插槽可以放入 0 到 50 之间的任意数字。

所以要求给定N，数组的大小，比如N=4，还有一个“范围”比如从1到6，我们做一个Iterator.new(4, 1..6)然后回来:

[1, 1, 1, 1]     

并且有办法做到iterator.next()然后回来

[1, 1, 1, 2]

继续做iterator.next()会得到我们

[1, 1, 1, 6]

和下一个iterator.next()会得到我们

[1, 1, 2, 1]

类似于6 + 1它不能容纳它，所以它重置为 1并结转到下一位数。

和iterator.next()最终会到达

[6, 6, 6, 6]

和下一个iterator.next()会得到我们

false  (or nil)

这个问题在计算机科学中是否有一个通用的名称？在 Ruby 中可能有什么简单的方法来解决这个问题？

现在我正在尝试使用递归来完成它，它看起来很复杂:

n = 4
a = 1
b = 6

arr = [a] * 4

def increment_position(arr, a, b, pos)

    return false if (pos >= arr.length)

    arr[-1 - pos] += 1

    if arr[-1 - pos] > b
        arr[-1 - pos] = a
        return increment_position(arr, a, b, pos + 1)
    else
        return arr
    end

end

def get_next_iteration(arr, a, b)
    return increment_position(arr, a, b, 0)
end

loop do
    p arr
    break if !get_next_iteration(arr, a, b)
end

附言该解决方案不应使用太多内存，例如仅字节、千字节或 MB。例如，它应该能够处理 Iterator.new(5, 0..50)或 Iterator.new(6, 0..50)很容易。

Answer 1

因此，您基本上需要 Range 的笛卡尔积与自身。这很容易做到:

def product_range_enumerator(num, range)
  range.to_a.product(*([range.to_a] * num.pred)).each
end

product_range_enumerator(4, 1..6)
# => #<Enumerator: ...>

enum = product_range_enumerator(4, 1..6)

enum.next
# => [1, 1, 1, 1]

enum.next
# => [1, 1, 1, 2]

# …

enum.next
# => [1, 1, 1, 6]

enum.next
# => [1, 1, 2, 1]

# …

enum.next
# => [6, 6, 6, 6]

enum.next
# StopIteration: iteration reached an end