2

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.

この例の問題は、最初の2つの組み合わせがすべて試行されるまで、3番目の位置がまったく探索されないことです。これを使用するコードでは、正しい答えは一般に（はるかに大きい）1,1,2ですが、それを見つける前に、数千ではなく数百万の可能性を調べます。

私は100万から数億の結果セットを扱っているので、それらを生成してから並べ替えることはここでは実行できず、最初の例でそれらを注文する理由を無効にします。以前のデカルト積生成から。

上記のいずれかを明確にするのに役立つ場合に備えて、これを今すぐ行う方法を示します（これは正しい結果と正しいパフォーマンスを示しますが、希望する順序ではありません。つまり、上記の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すべてが探求されるということです。

4

3 に答える 3

2

質問の精度の後で、ここに改訂版があります。前の回答も有用であり、それほど複雑でない順序を使用しているため、私は前の回答を保持しています。

# 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]]
于 2010-09-02T15:57:26.207 に答える
1

要素[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'）にアップグレードしてください。

于 2010-09-01T20:17:03.260 に答える
1

ちょっとマークアンドレ、デカルトの宝石はあなたが望むことを正確に行います：

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ドキュメントへのリンクがあります。

于 2011-01-03T18:14:47.753 に答える