Determine conflict-free sets?

Question

Suppose you have a bunch of sets, whereas each set has a couple of subsets.

Set1 = { (banana, pineapple, orange), (apple, kale, cucumber), (onion, garlic) }

Set2 = { (banana, cucumber, garlic), (avocado, tomato) }

...

SetN = { ... }

The goal now is to select one subset from each set, whereas each subset must be conflict free with any other selected subset. For this toy-size example, a possible solution would be to select (banana, pineapple, orange) (from Set1) and (avocado, tomato) (from Set2).

A conflict would occur, if one would select the first subset of Set1 and Set2 because the banana would be contained in both subsets (which is not possible because it exists only once).

Even though there are many algorithms, I was unable to select a suitable algorithm. I'm somehow stuck and would appreciate answers targeting the following questions:

1) How to find a suitable algorithm and represent this problem in such a way that it can be processed by the algorithm?

2) How a possible solution for this toy-size example may look like (any language is just fine, I just want to get the idea).

Edit1: I was thinking about simulated annealing, too (return one possible solution). This could be of interest to minimize, e.g., the overall cost of selecting the sets. However, I could not figure out how to make an appropriate problem description that takes the 'conflicts' into account.

Answer 1

This problem can be formulated as a generalized exact cover problem.

Create a new atom for each set of sets (Set1, Set2, etc.) and turn your input into an instance like so:

{Set1, banana, pineapple, orange}
{Set1, apple, kale, cucumber}
{Set1, onion, garlic}
{Set2, banana, cucumber, garlic}
{Set2, avocado, tomato}
...

making the Set* atoms primary (covered exactly once) and the other atoms secondary (covered at most once). Then you can solve it with a generalization of Knuth's Algorithm X.

Answer 2

Looking at the list of sets, I had the image of a maze with multiple entrances. The task is akin to tracing paths from top to bottom that are free of subset-intersections. The example in Haskell picks all entrances, and tries each path, returning those that succeed.

My understanding of how the code works (algorithm):

For each subset in the first set, pick each subset in the next set where the intersection of that subset with each of the subsets in the accumulated result is null. If there are no subsets matching the criteria, break that strain of the loop. If there are no sets left to pick from, return that result. Call the function recursively for all chosen subsets (and corresponding accumulating-results).

import Data.List (intersect)
import Control.Monad (guard)

sets = [[["banana", "pineapple", "orange"], ["apple", "kale", "cucumber"], ["onion", "garlic"]]
       ,[["banana", "cucumber", "garlic"], ["avocado", "tomato"]]]

solve sets = solve' sets [] where
  solve' []         result = [result]
  solve' (set:rest) result = do
    subset <- set
    guard (all null (map (intersect subset) result))
    solve' rest (result ++ [subset])

OUTPUT:

*Main> solve sets
[[["banana","pineapple","orange"],["avocado","tomato"]]
,[["apple","kale","cucumber"],["avocado","tomato"]]
,[["onion","garlic"],["avocado","tomato"]]]