algorithm - 「ほぼソートされた」または「kソートされた」リストを生成するアルゴリズム?

Question

「k 個のソート済み」リスト (各要素が正しいソート済み位置から最大 k 個の位置にあるリスト) を単一の完全にソート済みのリストにマージする関数をテストするためのテスト データを生成したいと考えています。私は機能するアプローチを持っていますが、それがどの程度ランダム化されているかはわかりません。これを行うには、よりシンプルでエレガントな方法があるはずです。私の現在のアプローチ：

1. 整数インデックスとペアになった n 個のランダム要素を生成します。
2. ランダムな要素を並べ替えます。
3. 各要素のペアのインデックスをソートされた位置に設定します。
4. 要素を逆方向に処理し、各要素を、リスト内の 1 ～ k 位置のランダムな距離の要素と交換します。ペアのインデックスが現在のインデックスである場合にのみ、ターゲット要素と交換します (これにより、既に場違いな要素を交換し、あるべき場所から k 位置よりも遠くに移動することを回避できます)。
5. 摂動要素を別のリストにコピーします。

私が言うように、これは機能しますが、代替/より良いアプローチに興味があります。

Answer 1

乱数の配列を生成し、それを shellsort のようにhソートできますが、 hがkより小さい場合、最後のソート手順はありません。

Answer 2

私が問題を理解していれば、長さのすべての並べ替えられたリストの宇宙から一様に選択された、k長さの単一の並べ替えられたリストをランダムに選択するアルゴリズムが必要です。(その後、このアルゴリズムを何度も実行して、入力テスト データとしてリストを生成します。)nUknmm

最初のステップは、それらを数えることです。の大きさはU？|U|

次のステップは、それらを列挙することです。F整数(1,2,...,|U|)とk長さの並べ替えられたリストの間の1 対 1 のマッピングを作成しますn。

x次に、1以上の整数をランダムに選択し、|U|適用F(x)してリストを取得します。