代码之家 › 专栏 › 技术社区 › Yuri Gadow

阵列深度一阶笛卡尔积的生成算法

cartesian-product algorithm ruby

Yuri Gadow · 技术社区 · 15 年前

我正在寻找一个示例,说明如何在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,它也会在找到它之前检查几百万种可能性,而不是几千种。

我处理的结果集是100万到数亿,所以生成它们然后排序在这里是不可行的,并且会破坏第一个例子中排序它们的原因,即更快地找到正确的答案,从而更早地跳出笛卡尔积生成。

为了帮助澄清上述任何一点,我现在就这样做(这有正确的结果和正确的性能,但不是我想要的顺序,即,它创建的结果如上面第二个列表所示):

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,以此类推。

3 回复 | 直到 15 年前

Marc-André Lafortune 15 年前

在问题的精确性之后,这里有一个修订版本。我保留前面的答案,因为它也可能有用,并且使用一个不太复杂的顺序。

# 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]]

Marc-André Lafortune 15 年前

不清楚元素在哪里 [1, 1, 3]

# yields the possible cartesian products of [first, *rest], where the total
# of the indices that are "distributed" is exactly +nb+.
def distribute(nb, first, *rest)
  if rest.empty?                    # single array remaining?
    yield first.fetch(nb) {return}  # yield the right element (if there is one)
  else
    first.each_with_index do |obj, i|
      break if i > nb
      distribute(nb - i, *rest) do |comb|
        yield [obj, *comb]
      end
    end
  end
end

def strange_cartesian(*arrays, &block)
  return to_enum __method__, *arrays unless block_given?
  max = arrays.map(&:length).inject(:+)
  max.times do |nb|
    distribute(nb, *arrays, &block)
  end
end

p strange_cartesian([1, 2, 3], [1, 2, 3], [1, 2, 3]).to_a
#  => [[1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 2, 2], [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]]

注意 :如果仍在运行Ruby 1.8.6,请至少升级到1.8.7(或 require 'backports'

Adriano Mitre 15 年前

嘿,马克·安德尔,那个 cartesian gem正是你想要的:

require 'cartesian'
[1,2,3].x([1,2,3]).to_a #=> [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

for a,b,c in [1,2,3]**3 ; p [a,b,c] ; end
# output:
#    [1, 1, 1]
#    [1, 1, 2]
#    [1, 1, 3]
#    [1, 2, 1]
#    ...
#    [3, 3, 3]

该项目托管在github上,在其文档中有一个到RDoc文档的链接 homepage .