Объедините все комбинации, чтобы получить полные комплекты - PullRequest
0 голосов
/ 18 февраля 2019

У меня есть массив:

arr = [1, 2, 3]

Я хочу найти все комбинации, а затем объединить комбинации, чтобы получить массивы, которые содержат все элементы arr только один раз.Последовательность не имеет значения.Первая комбинация должна возвращать что-то вроде

combis = [
  [1], [2], [3],
  [1, 2], [1, 3], [2, 3], 
  [1, 2, 3]
]

Мне нужно valid с комбинациями combis, которые содержат каждое значение из arr ровно один раз.Итак:

valid = [
  [[1], [2], [3]],
  [[1], [2, 3]],
  [[2], [1, 3]],
  [[3], [1, 2]],
  [[1, 2, 3]]
]

Это становится очень быстро, поэтому мне нужен способ сделать это без использования функции комбинации дважды, а затем отфильтровать неправильные.

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

Было бы здорово, если бы кто-то мог помочь мне с (псевдо) кодом для этого.

1 Ответ

0 голосов
/ 18 февраля 2019

Используйте Enumerator::Lazy для немедленного отклонения нежелательных / недействительных комбинаций:

combis = 1.upto(arr.size).each_with_object([]) do |i, acc|
  acc.concat arr.combination(i).to_a 
end 
#⇒ [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

valid = 1.upto(arr.size).each_with_object([]) do |i, acc|
  acc.concat(
    #                     ⇓⇓⇓⇓ THIS
    combis.combination(i).lazy.select do |e|
      items = e.flatten
      items.uniq.size == items.size && items | arr == items
    end.to_a
  )
end
#⇒ [[[1, 2, 3]], [[1], [2, 3]], [[2], [1, 3]], [[3], [1, 2]], [[1], [2], [3]]]
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...