より速く処理できる方法

Question

alphabet_array = ["e","d","c","b","a"]を何回置換させたら元の順序に戻るかを計算させたいです。
この例だと、
["e","d","c","b","a"]→["a","d","c","b","e"]→["a","b","c","d","e"]
1 2
で２回置換させたら元の順序に戻ることがわかります。
なので最終的に２回の２を出力させるアルゴリズムを作りたいです。

alphabet_array = ["e","d","c","b","a"]
backup = alphabet_array[:]
alphabet_array.sort()

count =0
for i in range(5):
   if alphabet_array[i] != backup[i]:
       count +=1
       x = backup.index(alphabet_array[i])
       backup[i], backup[x] = backup[x], backup[i]
print(count)

とコードを書いたのですがfor文のところで時間がかかってしまいます。
もっと速く処理できる方法（コード）はないでしょうか？

Comments

[_Victorique__]

Paizaの問題でしょうけど、アルゴリズムをもう少し見直してみてはいかがでしょう？こんな力技みたいなことはしなくて済みますよ

[退会済みユーザー]

Paizaの問題ではないです。修正点を探しているのですが、わからなくて...。具体的にどんなところを直せばいいとかキーワードで検索すればヒントが出てくるとかありましたら教えてください。

[_Victorique__]

失礼しました。次にした質問に関してはPaizaですよね？そこが分かっていないと迂闊に回答できませんので

[退会済みユーザー]

次にした質問がどのことかわからないのですが、ハノイの塔の質問はpaizaではなく、TypeErrorの方はpaizaででできたアルゴリズムを全く別のデータで試しているものです。

[_Victorique__]

こちらですね https://teratail.com/questions/82641

[退会済みユーザー]

はい、その質問は削除してもらっています。。。

Answer 1

文字列が２つあって、何度編集操作（文字の交換、文字の削除、文字の挿入）をすれば一方から他方に変換できるのかというのは、編集距離あるいはレーベンシュタイン距離(Levenshtein Distance)と呼ばれており、動的計画法(Dynamic Programing)で解ける問題の例として良く知られています。

編集距離 (Levenshtein Distance) の記事に詳細とコードが出ていますので、試してみてください。

Comments

[退会済みユーザー]

ありがとうございます。はってくださったリンクを見たのですが、なぜこの方法だとより早くできるのでしょうか？記述しているコードの量だけでいえば、質問文にはった私のコードの方が少ないように思えますが....。

[tamy]

計算が早いかはコード記述量より計算オーダーに依存します（もちろん簡潔な記述の方が早くなる傾向はあるけれども）．

で，計算オーダーで見ると，パッと見た限りだとどちらのコードも「入力された２つの文字列の長さの積」に依存するので，この指標ではコードの計算量は同程度ということになるかと思います．
実際はキャッシュの効き具合とかも出てくるので，きちんと計測して見なければどちらが早いかはわかりません．