0

1 から N までの自然数 (N は約 1e7) を持ち、値の範囲と比較して、かなり短いパラメーター セットによって定義される方法でセットを並べ替える関数を夢見ています。

N = 2^i - 1これは単なるビットの並べ替えである可能性があるため、 の値のみのセットがミューiテーションを0..i 定義します。

任意の N に適用できる、同様に美しい方法を探しています。

ビット並べ替えの例。8 つの値:0..7は 3 ビットでエンコードされます: 000 – 111. そのセットを並べ替えるために、各ビットの新しい位置を保存しました。配列[0,1,2]を取得してランダムに並べ替え、その結果を順列キーとして保存します。つまり[1,0,2]、次のように 8 つの値を並べ替えます。

   210   201   
0: 000 - 000 :0
1: 001 - 010 :2
2: 010 - 001 :1
3: 011 - 011 :3
4: 100 - 100 :4
5: 101 - 110 :6
6: 110 - 101 :5
7: 111 - 111 :7
4

3 に答える 3

3

N!コメントで特定されているように、順列の任意の 1 つを短いキーでエンコードできることに興味はありません。短いキーを指定して aa 順列を決定論的に選択する方法を探しているだけです。

あなたがする必要があるのは

  • お気に入りの疑似乱数ジェネレーターを選択します。
  • 既知の短いキーでシードします
  • Nアイテムのリストから値を選択するために使用します
于 2015-07-29T09:03:35.097 に答える
2

メモリを消費しない簡単な方法は、各数値に N と互いに素な定数を掛けてから、次のように N による除算の剰余を計算することです (Java の例)。

static int reorder(int input, int N) {
    // 15485863 is prime, thus coprime with any lesser N
    return (int) ((input * 15485863L) % N);
}

でのテストN = 10345560:

public static void main(String[] args) {
    int N = 10345560;
    int[] source = IntStream.range(0, N).toArray();
    int[] reordered = IntStream.of(source).map(i -> reorder(i, N)).toArray();
    // Check that all reordered numbers are within 0..N-1
    assert IntStream.of(reordered).allMatch(i -> i >= 0 && i < N);
    // Check that all numbers are different
    assert IntStream.of(reordered).distinct().count() == N;
}

利点は、すべての数値を格納するための中間メモリが必要ないことです。数値をストリーミング方式で処理できます (たとえば、あるファイルから読み取り、結果を別のファイルに書き込む)。

欠点は、指定されたパラメーターについて、それが N と互いに素であることをテストし、そうでない場合は拒否または調整する必要があることです。

于 2015-07-29T08:23:00.320 に答える