#arrays #algorithm
#массивы #алгоритм
Вопрос:
Придется немного повозиться. У меня есть реализация алгоритма методом перебора, который на самом деле не так сложен, но, очевидно, я хочу что-то более эффективное.
Проблема заключается в следующем:
Представьте, что у вас есть n массивов, каждый из которых заполнен некоторыми значениями от 1 до n. Что мне нужно, так это определить, возможно ли выбрать по одному элементу из каждого из этих массивов, таким образом, чтобы я выбирал каждый элемент от 1 до n ровно один раз. Небольшой пример: предположим, n = 4 и у нас есть эти n массивы:
[1,2,3,4]
[1,3]
[2,4]
[3,4]
Эта комбинация массивов прошла бы алгоритм, поскольку можно (например) выбрать 1, 3, 2, 4 из каждого массива соответственно. Другой возможностью было бы 2, 1, 4, 3.
Встречным примером может быть:
[1,2,3]
[3]
[3,4]
[3,4]
Здесь вы ясно видите, что эти входные массивы не прошли бы алгоритм. Невозможно выбрать 1 элемент из каждого массива таким образом, чтобы каждый элемент выбирался один раз.
Как я уже сказал, подход грубой силы не такой сложный, но я хочу что-то более эффективное, не проходя через все возможные перестановки, пока не найду ту, которая соответствует критериям.
Комментарии:
1. На каком языке вы программируете? Было бы лучше пометить ваш вопрос соответствующим языком, чтобы вы получали более целенаправленную помощь!
2. Как насчет «более простой» реализации, но также и грубой силы, простого двоичного дерева? первый
n/2будет проверен половиной входных данных, которые должны пройти тест, а другая половина — другой половиной входных данных! Просто предложение!3. несколько вопросов: 1 — всегда ли числа находятся в этом диапазоне
1 <= x <= n? 2- отсортированы ли массивы?4. @М.Каземахгари да и да. Итак, если у нас есть 3 массива, числа, которые могут быть в каждом, всегда равны 1,2,3. 5 массивов? 1,2,3,4,5 может быть во всех. И да, они будут отсортированы внутри массива.
5. @M.kazemAkhgary: все еще перебор … для каждой комбинации чисел в каждом массиве мне пришлось бы подсчитать, сколько раз они встречаются во всех массивах. Представьте себе 8 массивов, каждый из которых довольно заполнен числами. Мне пришлось бы выбирать каждую комбинацию из 2 чисел, каждую комбинацию из 3, каждую из 4 и так далее. Не очень эффективный.
Ответ №1:
Эта проблема может быть сведена к максимальному двудольному сопоставлению, которое может быть решено с помощью алгоритма Форда-Фулкерсона для задачи максимального потока:
Давайте создадим потоковый график 2*n узлов, в котором первый набор n узлов представляет массив, в то время как следующий набор n узлов представляют значения. Таким образом, будет ребро от узла i из первого набора к узлу j из второго набора тогда и только тогда, когда внутри массива i содержится значение j . Емкость для этого ребра должна быть равна 1, что означает, что вы можете выбрать только один из каждого массива.
После формирования этого графика примените классический алгоритм для поиска ответа.
Для примера в вопросе:
[1,2,3,4]
[1,3]
[2,4]
[3,4]
Мы можем сформировать этот график
Белые узлы представляют собой массивы, в то время как зеленые узлы представляют значения.
Комментарии:
1. На самом деле я думал о том, «будет ли это двудольной вещью» ранее. Определенно хорошее предложение. Получил реализацию этого из другого курса по алгоритмам, который я делал. Я попробую, спасибо!
2. Не могли бы вы, пожалуйста, нарисовать пример блок-схемы? Я этого не вижу 🙂
3. Работает просто отлично. Большое вам спасибо.