Алгоритм определения возможности выбора 1 уникального элемента из n массивов

Имейте немного ореха, чтобы взломать. У меня есть грубая реализация алгоритма, которая не так уж сложна, но, очевидно, я хочу что-то более эффективное.

Представьте, что у вас есть n массивов, каждый из которых заполнен значениями от 1 до n. Мне нужно определить, можно ли выбрать один элемент из каждого из этих массивов, чтобы я выбрал каждый элемент от 1 до n ровно один раз. Небольшой пример: предположим, что n = 4 и у нас есть эти n массивов:

Эта комбинация массивов будет соответствовать алгоритму, поскольку можно (например) выбрать 1, 3, 2, 4 из каждого массива соответственно. Другая возможность будет 2, 1, 4, 3. Контрпримером будет:

Здесь вы ясно видите, что эти входные массивы не проходят алгоритм. Невозможно выбрать 1 элемент из каждого массива таким образом, чтобы каждый элемент был выбран один раз.

Как я уже говорил, метод грубой силы не так уж и сложен, но я хочу что-то более эффективное, не пройдя все возможные перестановки, пока не найду тот, который соответствует критериям.

Ответы

Ответ 1

Эта проблема может быть сведена к максимальному двойному согласованию, которое может быть решено с помощью алгоритма Форда-Фулкерсона для задачи максимального потока:

Давайте создадим потоковый граф из 2*n узлов, причем первый набор из n узлов представляет массив, а следующий набор из n узлов представляет значения. Таким образом, будет ребро от узла i в первом наборе к узлу j во втором наборе тогда и только тогда, когда внутри массива i содержится значение j. Емкость для этого края должна быть 1, что означает, что вы можете выбрать только один из каждого массива.

После формирования этого графика примените классический алгоритм, чтобы найти ответ.

Для примера в вопросе:

[1,2,3,4]
[1,3]
[2,4]
[3,4]

Мы можем сформировать этот график

Белые узлы представляют собой массивы, а зеленые узлы представляют значения.