Мой коллега задал мне сложный вопрос, который, как мне кажется, является НП, но он не воспримет его как ответ.
Учитывая матрицу, определите, сколько существует неповторяющихся комбинаций цифр/букв, выбрав только одно число в столбце. Для этого неприемлема грубая сила (перебор всех возможных комбинаций). Он хочет найти формулу, которая решит эту проблему.
Например, он дал мне эту матрицу
1 2 2 3
2 3 3 4
3 4 4 5
4 5 5 6
Некоторые примеры результатов будут
1) 1 2 3 4
2) 1 2 3 5
3) 1 2 3 6
4) 1 3 2 4
5) 1 3 2 5
6) и тд...
Я написал java-программу, которая в основном состояла из 4 циклов for для прохождения всех возможных комбинаций (4x4x4x4 = 256 комбинаций), чтобы получить, я думаю, ответ был 36 возможных комбинаций. Но для него это неприемлемо. И для решения оно не может быть независимым только от одной матрицы, оно должно работать для всех n x n матриц.
Я ломал голову над этим, и я считаю, что проблема np (сложная / полная), потому что ее можно решить за полиномиальное время, но нет общего алгоритма, который вы могли бы сделать ... вам нужно переборщить.
Будем очень признательны за любую помощь/указатели/ссылки...
