ruby - 以深度优先顺序生成数组笛卡尔积的算法

Question

我正在寻找一个示例，说明如何在 Ruby 中使用类似 C 的语言或伪代码来创建可变数量的整数数组的笛卡尔积，每个整数数组的长度各不相同，并逐步处理结果一个特定的顺序:

给定 [1,2,3],[1,2,3],[1,2,3]:

[1, 1, 1]
[2, 1, 1]
[1, 2, 1]
[1, 1, 2]
[2, 2, 1]
[1, 2, 2]
[2, 1, 2]
[2, 2, 2]
[3, 1, 1]
[1, 3, 1]
etc.

而不是我见过的典型结果(包括我在下面给出的示例):

[1, 1, 1]
[2, 1, 1]
[3, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[1, 3, 1]
[2, 3, 1]
etc.

此示例的问题在于，在尝试了前两个位置的所有组合之前，根本不会探索第三个位置。在使用它的代码中，这意味着即使正确答案通常是(更大的等价物)1,1,2，它也会检查几百万种可能性，而不是在找到它之前只有几千种可能性。

我正在处理一百万到数亿的结果集，所以生成它们然后排序在这里是不可行的，并且会破坏在第一个示例中排序它们的原因，即更快地找到正确答案因此更早地突破了笛卡尔乘积世代。

以防万一它有助于澄清上述任何内容，下面是我现在的操作方法(这具有正确的结果和正确的性能，但不是我想要的顺序，即，它创建的结果与上面的第二个 list 一样):

def cartesian(a_of_a)
  a_of_a_len = a_of_a.size
  result = Array.new(a_of_a_len)
  j, k, a2, a2_len = nil, nil, nil, nil
  i = 0
  while 1 do
    j, k = i, 0
    while k < a_of_a_len
      a2 = a_of_a[k]
      a2_len = a2.size
      result[k] = a2[j % a2_len]
      j /= a2_len
      k += 1
    end

    return if j > 0
    yield result

    i += 1
  end

end

更新:我没有说得很清楚，我正在寻找一个解决方案，在添加 3 之前检查 1,2 的所有组合，然后是所有 3 和 1，然后是所有 3、2 和 1，然后是所有 3,2 .换句话说，在“垂直”之前先“水平”探索所有早期组合。探索这些可能性的精确顺序，即 1、1、2 或 2、1、1，并不重要，只是在混合 3 之前探索所有 2 和 1，依此类推。

Answer 1

在问题的精确性之后，这是一个修订版。我保留了之前的答案，因为它也很有用，而且使用的顺序不太复杂。

# yields the possible cartesian products of [first, *rest], where the total
# of the indices that are "distributed" is exactly +nb+ and each index doesn't
# go beyong +depth+, but at least one of them is exactly +depth+
def distribute(nb, depth, reached, first, *rest)
  from  = [nb - rest.size * depth, 0].max
  to    = [first.size-1, depth, nb].min
  from.upto(to) do |i|
    obj = first[i]
    reached ||= i == depth
    if rest.empty?
      yield [obj] if reached
    else
      distribute(nb - i, depth, reached, *rest) do |comb|
        yield [obj, *comb]
      end
    end
  end
end

def depth_first_cartesian(*arrays)
  return to_enum __method__, *arrays unless block_given?
  lengths = arrays.map(&:length)
  total = lengths.inject(:+)
  lengths.max.times do |depth|
    depth.upto(arrays.size * depth) do |nb|
      distribute(nb, depth, false, *arrays) {|c| yield c}
    end
  end
end

p depth_first_cartesian([1, 2, 3], [1, 2, 3, 4], [1, 2, 3]).to_a
# => [[1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 2, 2],
#     [1, 1, 3], [1, 3, 1], [3, 1, 1], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2],
#     [3, 2, 1], [1, 3, 3], [2, 2, 3], [2, 3, 2], [3, 1, 3], [3, 2, 2], [3, 3, 1], [2, 3, 3],
#     [3, 2, 3], [3, 3, 2], [3, 3, 3], [1, 4, 1], [1, 4, 2], [2, 4, 1], [1, 4, 3], [2, 4, 2],
#     [3, 4, 1], [2, 4, 3], [3, 4, 2], [3, 4, 3]]