Search code examples
algorithmbacktracking

Choose n unique elements from n lists

I have been thinking about a programing problem. If we have n lists, we want to output n diffrent elements (each one from a different list). I suspect this can be solved with some kind of a backtrack algorithm but I don't see how to correctly implement it.

Solution

  • Though you could solve this with backtracking as suggested in a comment, a more efficient solution would be to use a max-flow algorithm.
    Model it as a graph. A Source, a Sink a node for each distinct element and a node for each list. You have the source connected to each distinct element. Each element connected to every list it is in. and the lists connected to a sink node. Each edge with capacity 1.
    The maximum flow is the maximum number of distinct elements from distinct lists you can select.

    https://en.wikipedia.org/wiki/Maximum_flow_problem
    https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm