Оптимальное слияние строк чисел [закрыто] ⇐ JAVA

[Anonymous]

Я пытаюсь объединить столбцы чисел оптимальным способом. Цифры обозначают лошадей, на которых можно сделать ставку в скачках. Таким образом, каждая колонка представляет собой одиночную ставку на троттлинг. Желаемый результат — объединить их с купонами, используя как можно меньше купонов. Пример

Код: Выделить всё

1  1  1  1  1
3  3  2  2  2
4  6  6  4  5

Должно получиться два купона

Код: Выделить всё

1   1
23  2
46  5

Определение возможности объединения двух столбцов заключается в том, что они различаются только местом. Это означает, что одни и те же лошади участвуют во всех скачках, кроме одной, поэтому их можно объединить в один купон со всеми лошадьми из обеих колонок. Следовательно, 1,2,5 нельзя объединить, поскольку они в двух местах отличаются от остальных. Можно найти и другие решения, такие как

Код: Выделить всё

1   1
3   2
46  456

Проблема в достижении минимального количества наборов. Начальных наборов чисел может быть около 100 000, что делает исчерпывающий подход неэффективным. Если просто попробовать несколько случайных вариантов, то в качестве примера можно прийти сюда.

Код: Выделить всё

1   1   1
23  3   2
4   6   45

Сортируя по одному месту за раз, а затем сортируя наборы, можно прийти к результату, который я и сделал. Но это не оптимальное решение.

Подробнее здесь: https://stackoverflow.com/questions/791 ... of-numbers