Pseudo Random Number generator with fixed density

问题:

I'm searching for way to generate pseudo random numbers [possibly of low "randomness"] or pseudo random bit sequences with a fixed Hamming weight [ a fixed density of 1s]. I found some suggestion about using a simple linear congruential generator with a seed having the Hamming weight I need, but no reasoning was given why this is correct [why the hamming weight is invariant under the linear congruential transformation]

Could anyone reason that point or give me another way?

Thanks...

回答1:

I've not heard about using a LCG to generate a fixed hamming weight (I didn't get that deep into hamming codes at school, so I'm not too surprised either :).

In any case, it's fairly straightforward to generate a bunch of bits with a fixed hamming weight. Here's a bit of python code that will return an n-bit number with a particular weight. This should translate easily into other languages too (aside from the fact that python integers are arbitrarily large).

from random import randrange

def get_ham_and_bits(weight, nbits=32):
    "Get n-bits with a fixed hamming weight"
    if weight > nbits: 
        return 1 < nbits

    result = 0
    for i in xrange(weight):
        bit = 1 << randrange(nbits)

        # only flip bits that aren't already flipped. delete the loop to
        # make this return a random weight instead of a fixed weight
        while bit & result != 0: 
            bit = 1 << randrange(nbits)

        # An XOR might be a better idea here, especially if you remove the loop.
        result |= bit
    return result

回答2:

edit: python makes it easy to shuffle things

from random import shuffle

def gen(ham, bits=32):
    # generate a list with the correct number of 1's
    x = [1]*ham+[0]*(bits-ham)
    shuffle(x)
    # convert back to a number
    return int(''.join(map(str,x)),2)

>> print('\n'.join(bin(gen(5,15)) for x in range(10)))
0b101100100001000
0b100110010010
0b100110110000000
0b10010101100
0b11101100000
0b100100001000110
0b10000010101001
0b110000011100000
0b100011100010
0b100000011100010

---

Here's one possible way (basically, generate random permutations of a base string:

1. generate a random factoradic number N up to your bit-depth.
2. convert the factoradic to permutation index-list

3. convert your permutation list to bit-array (illustrated in pseudo-python):

   [x<weight for x in perm_list]

回答3:

Using a pseudo random number generator (PRNG) even a simple one with a low weight seed is definitely NOT a a good solution. The PRNG do not keep the Hamming weight of the seed constant, and the whole idea of a PRNG is to remove the information of the seed.

If you want to have exacly bits sets to 1 out of n, your question is a variant of these two questions. If k is much smaller than n, the shuffling solution is O(n). I think that the following solution is O(k).

It is based on this answer, in python

from random import sample

def konesoutofn(k, n):
    output=0
    for d in sample(xrange(n), k):output+=(1<<d)
    return output

x=konesoutofn(4,32)
print(bin(x))

If you want to have to have approximately k bits sets to one, with k/n being the probability of each bit to be one then you have to look at Bernouilli and Geometric distributions.