私の同僚は、私が NP だと思う挑戦的な質問をくれましたが、彼はそれを答えとして受け入れません。
行列が与えられた場合、列ごとに 1 つの数字のみを選択して、繰り返されない数字/文字の組み合わせがいくつあるかを判断します。このため、ブルート フォース (考えられるすべての組み合わせを試す) は受け入れられません。彼は、この問題を解決する公式が必要です。
たとえば、彼は私にこのマトリックスをくれました
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) など...
基本的に4つのforループで構成されたJavaプログラムを作成して、可能なすべての組み合わせ（4x4x4x4 = 256コンボ）を調べて、答えが36の可能なコンボであると信じています。しかし、彼にとってこれは受け入れられないことです。そして、ソリューションの場合、1 つのマトリックスだけに依存することはできず、すべての nxn マトリックスに対して機能する必要があります。
これについて頭を悩ませていて、多項式時間で解決できるため、問題はnp（ハード/完全）であると思いますが、実行できる一般的なアルゴリズムはありません...ブルートフォースする必要があります。
ヘルプ/ポインター/参照先は大歓迎です...