我正在寻找一个例子，用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，在找到它之前，它将检查几百万个可能性，而不是仅仅几千个。
我处理的是一百万到数亿的结果集，因此在这里生成它们然后进行排序是不可行的，并且会在第一个示例中击败排序它们的原因，第一个示例是更快地找到正确的答案，因此更早地从笛卡尔积成代中分离出来。
如果这有助于澄清以上任何一点，我现在就这样做（这有正确的结果和正确的性能，但不是我想要的顺序，即，它创建的结果如上面第二个清单所示）：
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，以此类推。
最佳答案
在问题精确之后，这里有一个修订版。我保留前面的答案，因为它也可能有用，而且使用的顺序也不那么复杂。
# 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]]
关于ruby - 深度优先生成数组笛卡尔积的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3621268/