我正在寻找一个示例,说明如何在 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/