☰

シャッフル強度インジケータに基づいてランダムなシャッフルシーケンスを取得するには？

tag-icon • tag-icon shell-script
シャッフル強度インジケータに基づいてランダムなシャッフルシーケンスを取得するには？

範囲内で一連のスクランブル要素を取得する必要がありますが、確かにしたいどのくらいこのシーケンスはスクランブルする必要があります。。たとえば、範囲がと仮定すると、1-10010個の数値シーケンスが必要です。次のシーケンスはすべて有効です。

{1,5,17,43,44,67,77,77,83,90}

{1,90,17,43,44,77,77,67,83,5}

{67,5,90,77,43,77,17,1,83,44}

ご覧のとおり、3つのシーケンスのすべての要素は同じですが、シャッフル強度は異なります。最初のシーケンスは整列され（つまりスクランブルされていない）、2番目のシーケンスは少しスクランブルされ、最後のシーケンスははるかにスクランブルされます（おそらくこのシーケンスだけが実際にスクランブルされている可能性があります：）。今、私はシャッフル強度インジケータまたはというインジケータに基づいてこれらのシーケンスを取得する方法が欲しいですsi2。

私の方法

この部分が私の問題を引き起こさないことを願っています。XYの問題。私は私のアプローチを共有したいだけで、質問のポイントではありません。しかし、このセクションの質問に対する回答が提供されていることを嬉しく思います。

2,000,000の範囲の一連の数値を取得するには、次の一連のコマンドを使用しました1-2000000。

for i in `seq 10000`; do 
    shuf -i 1-2000000 -r -n 100 | sort ; shuf -i 1-2000000 -r -n 100; 
    done > input

ご覧のとおり、シーケンスには100個の数字からなる10,000個のブロックがあります。たとえば、150最初の代わりに100250番目の代わりに使用できます。混合力4倍になります。しかし、このアプローチには（少なくとも私にとっては）いくつかの問題があります。

  • この方法は遅すぎる（そして理由を知りたいです。チャンクが大きいほど作業速度が速くなることがわかりました。 ）。
  • それも必要です手動測定シャッフルの強度を表す 2 つの数字の 1 つです。
  • そしておそらく最も重要なことは、実際にはランダムシャッフルではありません。。ご覧のとおり、ブロックサイズは同じです。

理想的なソリューション

理想的には、次のオプションを含むスクリプトが必要です。

myshuf SI2 MIN MAX NUM [OUTPUT]

whileは、シーケンスの混合強度を表すシーケンスの範囲とサイズをMIN決定します。高いほど、シャッフルが強くなります。 0から10の間になります。 MAXNUMSI2SI2SI2

だから

myshuf 0 0 2000000 2000000

0 ～ 2,000,000 の 2,000,000 個の数字からなる順序付きシーケンスを提供します。

myshuf 10 0 2000000 2000000

本当に素晴らしいシャッフルシーケンスを提供します。

なぜそのようなシーケンスが必要なのか疑問に思ったら、私はいくつかのソートアルゴリズムを持っていて、それぞれを試してみて、さまざまなタイプの入力の時間複雑さを確認したいと思います。

答え1

さまざまな強度で混合する1つの方法は、ソートされたリストを使用してさまざまな数のランダムな置換を実行することです（要素が複数回移動されないようにする）。

shuffle() {
  awk -v n="$1" '
    {line[NR]=$0; i[NR] = NR}
    END{
      if (n > NR/2) {
        print "two many permutations"
        exit(1)
      }
      srand()
      for (x = 1; x <= NR; x++) {
        # shuffle the list of indicies
        y = int(rand() * NR) + 1
        tmp = i[x]; i[x] = i[y]; i[y] = tmp
      }
      for (x = 1; x <= n; x++) {
        # get the lines to permute from the head of the shuffled
        # list of indices
        y = i[x*2-1]; z = i[x*2]
        tmp = line[y]; line[y] = line[z]; line[z] = tmp
      }
      for (x = 1; x <= NR; x++) print line[x]
    }'
}

$ seq 10 | shuffle 0 | paste -sd , -
1,2,3,4,5,6,7,8,9,10
$ seq 10 | shuffle 1 | paste -sd , -
1,2,6,4,5,3,7,8,9,10
$ seq 10 | shuffle 5 | paste -sd , -
9,6,5,10,3,2,8,7,1,4

shuffle 5どの要素も元の位置を維持しないことを保証します（シャッフルはn2 * n要素が異なる位置を取得することを保証します）。決して達成できないシャッフルがあります。たとえば、リスト1、2、3の場合、可能な結果は、2,1,3および3,2,1のみです1,3,2。いいえ3,1,2

これにより、混乱が少なくなる可能性がある結果が得られますshuffle 5。6,7,8,9,10,1,2,3,4,5

関連情報