Алгоритм получения декартовых произведений массивов в порядке глубины

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, он найдет несколько миллионов возможностей вместо нескольких тысяч, прежде чем найдет его.

Я имею дело с наборами результатов от одного миллиона до сотен миллионов, поэтому генерация их и последующая сортировка здесь неосуществимы, и в первом примере будет устранена причина их упорядочения, а именно, чтобы быстрее найти правильный ответ и т. Д.вырваться из поколения декартовых произведений ранее.

На всякий случай, если это поможет прояснить любое из вышеперечисленного, вот как я это делаю сейчас (это дает правильные результаты и правильную производительность, но не тот порядок, который я хочу, т.е.это создает результаты, как во втором листинге выше):

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

ОБНОВЛЕНИЕ : я не очень ясно дал понять, что я ищу решение, где все комбинации 1,2 проверяются до добавления 3, затем все 3 и 1, затем все 3, 2 и 1, затем все 3,2.Другими словами, исследуйте все более ранние комбинации «по горизонтали» перед «по вертикали».Точный порядок, в котором исследуются эти возможности, т. Е. 1,1,2 или 2,1,1, не имеет значения, просто все 2 и 1 изучаются до смешивания в 3 и т. Д.

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

Answer 2

Эй, Марк-Андре, декартовый драгоценный камень делает именно то, что вы хотите:

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

Вы также можете использовать оператор ** (power) для краткости

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.

Answer 3

Непонятно, куда входит элемент [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')