CODEWITHSUNDEEP
rubyalgorithm
Sander Schepens
Sander Schepens

Reputation: 73

Combine all combinations to get complete sets

I have an array:

arr = [1, 2, 3]

I want to find all combinations and then combine the combinations to get arrays that contain all the elements of arr only once. The sequence doesn't matter. The first combination should return something like

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

I need valid that has the combinations of combis that contain each value from arr exactly once. So:

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

This gets large very quickly, so I need a way to do this without using the combination function twice and then filtering out the incorrect ones.

I feel I need to use some kind of tree structure and recursion to generate the second set of combinations and stop traversing when it is no longer a valid final set.

Would be great if someone could help me with the (pseudo)code for this.

Upvotes: 3

Views: 111

Answers (1)

Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 121000

Use Enumerator::Lazy to reject unwanted / invalid combinations immediately:

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

Upvotes: 4

Related Questions