PRNG untuk menghasilkan angka dengan n mengatur bit dengan tepat

Saat ini saya sedang menulis beberapa kode untuk menghasilkan data biner. Saya secara khusus perlu menghasilkan angka 64-bit dengan jumlah bit yang ditentukan; lebih tepatnya, prosedur harus mengambil beberapa $0 < n < 64$ dan mengembalikan nomor pseudo-acak 64-bit dengan tepat $n$ bit diatur ke $1$ , dan sisanya diatur ke 0.

Pendekatan saya saat ini melibatkan sesuatu seperti ini:

1. Hasilkan angka pseudorandom 64-bit $k$ .
2. Hitung bit dalam $k$ , menyimpan hasilnya dalam $b$ .
3. Jika $b = n$ , output $k$ ; kalau tidak pergi ke 1.

Ini berfungsi, tetapi tampaknya tidak elegan. Apakah ada semacam algoritma PRNG yang dapat menghasilkan angka dengan $n$ menetapkan bit lebih elegan dari ini?

Yang Anda butuhkan adalah angka acak antara 0 dan . Masalahnya kemudian adalah mengubah ini menjadi pola bit.${ 64 \choose n } - 1$

Ini dikenal sebagai enumerative coding, dan ini adalah salah satu algoritma kompresi yang digunakan tertua. Mungkin algoritma paling sederhana adalah dari Thomas Cover. Ini didasarkan pada pengamatan sederhana bahwa jika Anda memiliki kata yang panjangnya bit, di mana bit yang adalah dalam urutan bit paling signifikan, maka posisi kata ini dalam urutan leksikografis semua kata dengan properti ini adalah:x k … x $n$$x_k \ldots x_1$

Jadi, misalnya, untuk kata 7-bit:

i(0001011)= (

...dan seterusnya.

Untuk mendapatkan pola bit dari ordinal, Anda cukup mendekodekan setiap bit secara bergantian. Sesuatu seperti ini, dalam bahasa seperti-C:

uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

Perhatikan bahwa karena Anda hanya membutuhkan koefisien binomial hingga 64, Anda dapat melakukan precompute.

• Sampul, T., Pengkodean Sumber Enumeratif . Transaksi IEEE pada Teori Informasi, Vol IT-19, No 1, Jan 1973.

Sangat mirip dengan jawaban Pseudonim, diperoleh dengan cara lain.

Jumlah total kombinasi yang tersedia dapat didekati dengan metode bintang dan balok , sehingga harus . Jumlah total angka 64-bit dari mana Anda akan mencoba untuk mengambil sampel nomor Anda akan jauh lebih tinggi dari itu.$c=\binom{64}{n}$

Yang Anda butuhkan adalah fungsi yang dapat mengarahkan Anda dari angka pseudorandom , mulai dari hingga , hingga kombinasi 64-bit yang sesuai.1 $k$$1$$c$

Segitiga Pascal dapat membantu Anda dengan hal itu, karena nilai setiap simpul mewakili jumlah persis jalur dari simpul tersebut ke akar segitiga, dan setiap jalur dapat dibuat untuk mewakili salah satu string yang Anda cari, jika semua belokan kiri adalah diberi label dengan , dan setiap belokan kanan dengan .$1$$0$

Jadi, biarkan menjadi jumlah bit yang tersisa untuk ditentukan, dan menjadi jumlah yang tersisa untuk digunakan.$x$$y$

Kita tahu bahwa , dan kita dapat menggunakannya untuk menentukan bit nomor berikutnya dengan benar di setiap langkah:$\binom{x}{y}=\binom{x-1}{y}+\binom{x-1}{y-1}$

$\mathtt{while}\;\;\; x>0$

$\quad \mathtt{if}\;\;\; x>y$

$\qquad \mathtt{if}\;\;\;k>\binom{x-1}{y}: \;\;\;s \leftarrow s\; + \mathtt{"1"}, \;k\leftarrow k-\binom{x-1}{y}, \;y \leftarrow y-1$

$\qquad \mathtt{else}:\; \;s \leftarrow s\; + \mathtt{"0"}$

$\quad \mathtt{else}: \;\;s \leftarrow s\; + \mathtt{"1"}, \;y \leftarrow y-1$

$\quad x \leftarrow x-1$

Metode lain yang cukup elegan adalah dengan menggunakan pembagian dua seperti yang dijelaskan dalam jawaban stackoverflow ini . Idenya adalah untuk menjaga dua kata, satu diketahui memiliki paling banyak bit k set dan satu diketahui memiliki setidaknya bit k set, dan menggunakan keacakan untuk memindahkan salah satu dari ini ke arah memiliki bit k yang tepat. Berikut ini beberapa kode sumber untuk menggambarkannya:

word randomKBits(int k) {
    word min = 0;
    word max = word(~word(0)); // all 1s
    int n = 0;
    while (n != k) {
        word x = randomWord();
        x = min | (x & max);
        n = popcount(x);
        if (n > k)
            max = x;
        else
            min = x;
    }
    return min;
}

Saya membuat perbandingan kinerja berbagai metode dan ini biasanya yang tercepat kecuali k diketahui sangat kecil.

Anda dapat melakukan hal berikut:

1) Menghasilkan angka acak, antara dan .$k$$1$$64$

2) Tetapkan ke ke .$k$$0$$1$

3) Ulangi langkah 1 dan 2 kali$n$

$A[]$ adalah array bit dengan semua dtk$64$$0$

for(i=1 to n)
{
    k=ran(1,65-i) % random number between 1 and 65-i
    for(x=1;x<65;x++)
    {
        if(A[x]==0)k--;
        if(k==0)break;
    }
    A[x]=1;
}