如何遍历一系列可能的整数,例如从[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

PS解决方案不应使用太多内存,例如字节,千字节或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