11

N 個の数字が与えられ、その順序について M 個のルールを適用します。ルールはインデックスのペアで表され、すべてのペア (A、B) は、インデックス A の数字 (A 番目の数字) が B 番目の数字の後にある必要があることを示しています - それは彼の隣にある必要はありません.

Ex: N = 4
    1 2 3 4
    M = 2
    3 2
    3 1

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:)

アルゴリズムは、例のように、ルールに違反しない利用可能なすべての順列を提供する必要があります-3 は常に 2 の後と 1 の後にある必要があります。

ブルートフォースを試してみましたが、うまくいきませんでした (ここではブルートフォースが機能するはずですが、N は (1,8) の範囲にあります)。

何か案は ？

4

3 に答える 3

9

ヒントとして。

ルールのセットをグラフとして扱うことができます。各インデックスは頂点であり、各ルールは有向エッジです。

番号の適切な順序（つまり、規則を満たす順列）は、上記のグラフのいわゆるトポロジカル順序に対応します。番号のすべての有効な順序を生成するには、そのグラフのすべての可能なトポロジ順序を生成する必要があります。

PSリンクされたウィキペディアのページで提供されているトポロジカル順序付けの最初のアルゴリズムは、すべての有効な順列を列挙するかなり簡単なソリューションをすでに可能にしています。実装にはある程度の努力と注意が必要ですが、ロケット科学ではありません。

于 2010-02-27T00:44:59.933 に答える
4

ブルートフォーシングは、すべての順列（O（N！））を通過し、各順列について、すべてのルールをループして、それらがAplpy（O（M））であることを確認します。これは、一種のばかげたO（N！M）になりますが、このような小さなセットでは「機能しない」はずです。

于 2010-02-27T00:49:08.553 に答える
1

正直なところ、あなたの最善の策は、戻ってブルートフォースソリューションを機能させることです. それが完了したら (まだ時間があれば)、より良いアルゴリズムを探すことができます。

反対投票者に編集します。その生徒は宿題を時間通りに終わらせようとしている（すべきである）。どうやら、彼の宿題は力ずくの解決策で十分なプログラミング演習です。彼が効率的なアルゴリズムを理解するのを助けることは、彼の本当の問題に対処することではありません。

この場合、彼は単純な力ずくのアプローチ (誰もが小さなN値で機能することに同意するはずです) を試みましたが、おそらくもっと難しいことを試みるために時期尚早にそれをあきらめました。経験豊富な開発者なら誰でも、これは悪い考えだと言うでしょう。生徒はそう言われる必要があり、そう言われるに値します。しかし、明らかに、それは彼の選択です...

于 2010-02-27T01:14:03.843 に答える