Pick elements from list of sets to cover all sets with exactly one element

user_15853075 0
Viewed 91

I am looking for the idiomatic and fast python solution for the following problem. Input is a list of sets. For example, 3 sets of strings.

[
{a, b, c, d, e},
{a, c, e, f, g},
{e, f, a, d, l}
]

I would like to find all choices of string combinations so that there is only one element in combination per set.

For example, these are "mappings" that show at what list positions these strings occur:

a -> 0, 1, 2
b -> 0
c -> 0, 1
d -> 0, 2
e -> 0, 1, 2
f -> 1, 2
g -> 1
l -> 2

So the correct solution is the following list of sets

a
b, g, l
b, f
e
c, l
d, g

Here are some examples of incorrect solutions:

a, b # incorrect because more than one element (2) from set 0 are used
b, l # incorrect because less than one element (0) from set 1 is used

I tried naive recurrent solution that adds one element at a time from the row and then checks remaining rows if they met requirements or not. It was extremely slow (probably because I overused list concatenations, copies, etc). I am looking for the solution that will work relatively fast (less than 10 s) for 100 rows of sets where each of them has 50 elements in average.

As noted in the comments this problem may not be solvable in finite time with these constraints. In that case I am still interested in the python solution that will work with weaker constraints (e.g. alphabet size 30, average set size 10, number of sets 50).

python
1 Answers

I would use a SAT solver like z3 for this.

import z3

sets = [
    {"a", "b", "c", "d", "e"},
    {"a", "c", "e", "f", "g"},
    {"e", "f", "a", "d", "l"}
]

alphabet = set.union(*sets)
zvars = {w: z3.Bool(w) for w in alphabet}

sol = z3.Solver()
for s in sets:
    # Exactly one in each set.
    sol.add(z3.PbEq([(zvars[w], True) for w in s], 1))

# Iterate over all solutions.
while sol.check() == z3.sat:
    model = sol.model()
    print({w for w, v in zvars.items() if bool(model[v])})

    # Prevent same solution being returned.
    trues = [v for v in zvars.values() if bool(model[v])]
    falses = [z3.Not(v) for v in zvars.values() if not bool(model[v])]
    sol.add(z3.Not(z3.And(trues + falses)))

Solution:

{'e'}
{'g', 'd'}
{'g', 'b', 'l'}
{'b', 'f'}
{'c', 'l'}
{'a'}
user_5656350
Related