PRNG для генерации чисел с n установленными битами точно

В настоящее время я пишу код для генерации двоичных данных. Мне конкретно нужно генерировать 64-битные числа с заданным количеством установленных битов; Точнее, процедура должна занять около $0 < n < 64$ и вернуть псевдослучайное 64-битное число с точно $n$ битами, установленными в $1$ , а остальные - в 0.

Мой текущий подход включает в себя что-то вроде этого:

1. Генерация псевдослучайного 64-битного числа $k$ .
2. Посчитайте биты в $k$ , сохранив результат в $b$ .
3. Если $b = n$ , выведите $k$ ; в противном случае перейдите к 1.

Это работает, но, кажется, не элегантно. Существует ли какой-нибудь алгоритм PRNG, который может генерировать числа с $n$ установленными битами более элегантно, чем этот?

Вам нужно случайное число от 0 до . Проблема тогда состоит в том, чтобы превратить это в битовую комбинацию.${ 64 \choose n } - 1$

Это известно как перечислительное кодирование, и это один из самых старых развернутых алгоритмов сжатия. Вероятно, самый простой алгоритм от Томаса Ковер. Это основано на простом наблюдении, что если у вас есть слово длиной битов, где заданные биты в порядке разрядов, то позиция этого слова в лексикографическом порядке всех слов с этим свойством является:x k … x $n$$x_k \ldots x_1$

Так, например, для 7-битного слова:

i(0001011)= (

...и так далее.

Чтобы получить битовый шаблон из порядкового номера, вы просто декодируете каждый бит по очереди. Примерно так, на 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;
}

Обратите внимание, что поскольку вам нужны только биномиальные коэффициенты до 64, вы можете их предварительно вычислить.

• Cover, T., Enumerative Source Encoding . IEEE Труды по теории информации, том IT-19, № 1, январь 1973 г.

Очень похоже на ответ псевдонима, полученный другими способами.

$c=\binom{64}{n}$

$k$$1$$c$

$1$$0$

$x$$y$

$\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$

Еще один довольно элегантный метод - использовать разделение пополам, как описано в этом ответе stackoverflow . Идея состоит в том, чтобы сохранить два слова, одно из которых имеет не более k установленных битов, а другое - как минимум k установленных битов, и использовать случайность, чтобы переместить одно из них к точно k битам. Вот некоторый исходный код, чтобы проиллюстрировать это:

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;
}

Я провел сравнение производительности различных методов, и этот метод, как правило, самый быстрый, если известно, что k очень мало.

Вы можете сделать следующее:

1) Генерация случайного числа, между и .1 $k$$1$$64$

2) Установите th на .0 $k$$0$$1$

3) Повторите шаги 1 и 2 раз$n$

64 $A[]$ - это битный массив со всеми с$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;
}