最小編集距離で効率的なランダムシーケンスを作成する

Question

編集距離が最小のランダムシーケンス（4文字の異なる20文字の長さのシーケンス）を作成するためのプログラム/スクリプトを作成する必要がありますすべての配列。 「高」はここでは100kシーケンスの最小値ですが、可能な場合は100万までです。

ランダムな20文字のシーケンスを生成するという単純なアプローチから始まり、シーケンスごとに、すでに作成され保存されている他のすべてのシーケンスとの編集距離を計算します。新しいシーケンスが自分のしきい値を超えた場合は保存し、それ以外の場合は破棄します。

理解していただいたように、これはシーケンスの数が増えるほど非常に大きくなります。最大10kまでは問題ありませんが、100kを取得しようとすると面倒です。

実際にはシーケンスを一度作成して出力する必要があるので、スピードについてはそれほど難しいことではありませんが、今日このレートで100万を作成することは、まったく不可能です。

シーケンスを構築するなどのプロセスをスピードアップするための代替案を考えようとしてきたが、最小限のEDの「ブロック」であり、結合するが、解決策は出ていない。

驚くべきことに、誰かが、最小限のEDで時間のかかる効率的なシーケンスを作成するために実装できるスマートなアイデアや方法はありますか？

乾杯、 JB

Answer 1

それはそう、ウィキペディアから、その編集距離は、3つの操作の挿入、削除、置換の一つです。開始文字列に対して実行されます。なぜ体系的にはすべての文字列を開始文字列から編集し、制限に達すると停止しますか？

実際の編集距離が世代別に正しいと確認する必要はありません。ランダム性のために、数値を生成してからそれらをシャッフルすることができます。