4

次のようなペアのリストがあります

[[4,1],[1,2],[2,3]]

アイデアは、最初のノードの 2 番目のインデックスが 2 番目の最初のノードと一致するようにそれらを並べ替えることです。この例では、リストがソートされています。リストは常にこの形式に一意に入れることができると想定されています。リストは循環的ではありません。

さて、可能であれば、次の方法でcompareこのフォームを取得できるコンパレーターが必要です。

x = [[4,1],[1,2],[2,3]]

x.sort(compare)

関数compareが「大きい」と「小さい」に対応する 2 つの値のいずれかを返すとします。これは可能ですか?可能であれば、ソートアルゴリズムに依存しますか?

不可能な場合は、2 つのパス (おそらく異なるコンパレーターを使用) または任意の固定数のパスで実行できますか。

私はこれをpythonで書きましたが、私の質問は具体的なものではありません。

4

1 に答える 1

8

必要な順序は厳密な半順序ではないため、これを 1 回のパスで行うことはできません。具体的には、コンパレータが機能するためには、いくつかのプロパティに従う必要があります。

  1. 非反射性: 要素は、それ自体よりも小さい比較をすることはありません。
  2. 非対称性: a が b より小さい場合、b は a より小さいとは比較されません。
  3. 推移性: a が b 未満を比較し、b が c 未満を比較する場合、c は a 未満を比較しません。

あなたのケースでは、これらの 3 つのプロパティすべてに違反しています。

  1. [1, 1] は、[1, 1]、[1, 1] を連鎖できるため、それ自体より少ない比較を行います。
  2. [1, 4] チェーンは [4, 1] に、[4, 1] チェーンは [1, 4] に、2 つの要素を相互にチェーンできます。
  3. 推移性は成立しません: [1, 2] は [2, 3] と連鎖し、[2, 3] は [3, 4] と連鎖しますが、[1, 2] は [3, 4] と連鎖しません。

問題をモデル化するより良い方法は、グラフを通るオイラー経路を見つけようとすることです。オイラー パスは一連のリンクをたどる方法であるため、リンクをたどることはなく、すべてのリンクをたどることができます。(「線をたどったり、鉛筆を手に取ったりせずにこの図を描く」パズルをしたことがあるなら、それはほとんど同じ考えです。) あなたの場合、リンクは [a, b] のペアであり、それらを通るチェーンです。オイラーパスと同じです。幸いなことに、オイラー パスを見つけるための優れた効率的なアルゴリズムが数多くあります。これらのアルゴリズムは、まさにこのコンテキストで探しているものだと思います。

お役に立てれば！

于 2013-06-14T02:16:33.960 に答える