PRNG do generowania liczb z n dokładnie ustawionymi bitami

Obecnie piszę kod do generowania danych binarnych. W szczególności muszę wygenerować liczby 64-bitowe przy określonej liczbie ustawionych bitów; dokładniej, procedura powinna zająć około i zwrócić pseudolosową 64-bitową liczbę z dokładnie bitami ustawionymi na , a resztą ustawioną na 0.$0 < n < 64$$n$$1$

Moje obecne podejście obejmuje coś takiego:

1. Wygeneruj pseudolosowy 64-bitowy numer .$k$
2. Policz bity w , przechowując wynik w .$k$$b$
3. Jeśli , wyprowadza ; w przeciwnym razie przejdź do 1.$b = n$$k$

To działa, ale wydaje się nieeleganckie. Czy istnieje jakiś algorytm PRNG, który może generować numery z bitów ustawionych bardziej elegancko niż to?$n$

Potrzebujesz losowej liczby od 0 do . Problem polega zatem na przekształceniu tego w wzór bitowy.${ 64 \choose n } - 1$

Jest to znane jako kodowanie wyliczeniowe i jest to jeden z najstarszych wdrożonych algorytmów kompresji. Prawdopodobnie najprostszy algorytm pochodzi od Thomasa Covera. Opiera się na prostej obserwacji, że jeśli masz słowo o długości bitów, gdzie ustawione bity to w najbardziej znaczącej kolejności bitów, to pozycja tego słowa w porządku leksykograficznym wszystkich słów o tej właściwości jest:x k … x $n$$x_k \ldots x_1$

Na przykład 7-bitowe słowo:

...i tak dalej.

Aby uzyskać wzór bitowy z porządkowej, po prostu dekodujesz kolejno każdy bit. Coś takiego w języku 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;
}

Pamiętaj, że ponieważ potrzebujesz tylko współczynników dwumianowych do 64, możesz je wstępnie obliczyć.

• Cover, T., Enumerative Source Encoding . Transakcje IEEE dotyczące teorii informacji, tom IT-19, nr 1, styczeń 1973.

Bardzo podobny do odpowiedzi Pseudonim uzyskanej w inny sposób.

Całkowitą liczbę dostępnych kombinacji można uzyskać metodą gwiazdek i słupków , więc będzie to musiało wynosić . Całkowita liczba 64-bitowych liczb, z których próbujesz próbkować swoją liczbę, byłaby oczywiście znacznie wyższa.$c=\binom{64}{n}$

Potrzebujesz zatem funkcji, która może poprowadzić cię od pseudolosowej liczby , od do , do odpowiedniej kombinacji 64-bitowej.1 $k$$1$$c$

Trójkąt Pascala może ci w tym pomóc, ponieważ wartość każdego węzła reprezentuje dokładnie liczbę ścieżek od tego węzła do pierwiastka trójkąta, a każda ścieżka może być reprezentowana przez jeden z ciągów, których szukasz, jeśli wszystkie skręty w lewo są oznaczone , a każdy skręt w prawo .$1$$0$

Niech będzie liczbą bitów pozostałych do ustalenia, a liczbą pozostałych do użycia.$x$$y$

Wiemy, że , i możemy go użyć, aby poprawnie określić następny bit liczby na każdym kroku:$\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$

Inną dość elegancką metodą jest użycie bisekcji, jak opisano w tej odpowiedzi na przepełnienie stosu . Pomysł polega na zachowaniu dwóch słów, z których jedno ma co najwyżej k bitów, a drugie co najmniej k bitów, i używa losowości, aby przesunąć jedno z nich w kierunku uzyskania dokładnie k bitów. Oto kod źródłowy, który to ilustruje:

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

Zrobiłem porównanie skuteczności różnych metod i ten jest zwykle najszybszym chyba k jest znany jako bardzo małe.

Możesz wykonać następujące czynności:

1) Wygeneruj liczbę losową, od do .1 $k$$1$$64$

2) Ustaw th na .0 $k$$0$$1$

3) Powtórz kroki 1 i 2 razy$n$

64 $A[]$ to tablica bitowa ze wszystkimi s$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;
}