0

私は単純な問題を求めています: 複雑さが最も低い一連の数字 (繰り返しを含む) で 1 つ (そして 1 つだけ) の順列を見つける方法は?

シーケンスがあるとします: 1 1 2 3 4. 次に、2 と 3 を並べ替えると、次のようになります1 1 3 2 4。2 と 3 が並べ替えられていることを確認するにはどうすればよいですか? 最悪の解決策は、すべての可能性を生成し、それぞれを元の並べ替えられたシーケンスと比較することですが、何か速いものが必要です...

ご回答ありがとうございます。

4

3 に答える 3

1

これに関する問題は、順序が順番に見つかるなどの制約なしに、問題に対する複数の解決策があることです。

私が見たいのは、シーケンスに同じ値がまだあることを最初にテストし、そうであれば、不一致が見つかるまで1つずつステップスルーし、他の値の最初の出現場所を見つけて、それを順列。次に、次の変更などの検索を続けます...

どれだけ変化したか知りたいだけなら、レーベンシュタインアルゴリズムを見てください。このアルゴリズムの基礎は、独自のカスタム アルゴリズムに必要なものを提供したり、他のアプローチを刺激したりすることさえあります。

これは高速ですが、どの項目が変更されたかはわかりません。

私が知っている唯一の完全な解決策は、変更が発生するたびに記録し、変更の履歴を見て完璧な答えを知ることです。

于 2012-11-07T10:05:55.530 に答える
0

元の配列と派生配列の間にスワップが1つしかない場合は、配列の長さnに対してO（n）で次のようなことを試すことができます。

int count = 0;
int[] mismatches;

foreach index in array {
    if original[index] != derived[index] {
        if count == 2 {
            fail
        }
        mismatches[count++] = index;
    }
}

if count == 2 and
   original[mismatches[0]] == derived[mismatches[1]] and
       original[mismatches[1]] == derived[mismatches[0]] {

    succeed
}

fail

アレイ間で何も交換されなかった場合、これは失敗を報告することに注意してください。

于 2012-11-07T11:41:05.080 に答える
0 
function findswaps:
    linkedlist old <- store old string in linkedlist
    linkedlist new <- store new string in linkedlist

    compare elements one by one:
        if same
             next iteration until exhausted
        else
             remember old item
             iterate through future `new` elements one by one:
                 if old item is found
                     report its position in new list
                 else
                     error

私の謙虚な試みが間違っている場合は修正してください。データは順序付けられていないと推測しているので、線形よりも高速になることはありませんか?

于 2012-11-07T10:04:21.250 に答える