1s fixed-density pseudo-random number generator

Question

I am looking for a way to generate pseudo-random numbers [possibly with a low “randomness”] or pseudo-random bit sequences with a fixed Hamming weight [fixed density 1 s]. I found some suggestion on using a simple linear congruent seed generator with a Hamming weight I need, but no explanation was given why this is correct [why the weight of the sigh is invariant with respect to the linear congruent transformation]

Can anyone reason about this or give me another way?

Thanks...

Answer 1

edit : python simplifies shuffling 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 is one of the possible ways (basically, to generate random permutations of the base line:

• generate a random factor number N to your depth.
• converts factorial to permutation index list

• convert the permutation list to a bit array (shown in pseudo python):

  [x <weight for x in perm_list]

Answer 2

I have not heard about using LCG to create a fixed weight for hacking (I did not understand what is deep in the code for haming at school, so I'm not surprised either :).

In any case, it's pretty simple to create a bunch of bits with a fixed weight. Here is some python code that will return an n-bit number with a specific weight. It is also easy to translate into other languages ​​(except that the integers in python 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 

Answer 3

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

If you want cue ball with a fast value to be set to 1 of n, your question is a variant of these two questions. If k is much less than n, then the shuffle is O (n). I think the next 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 approximately k bits of sets equal to one, then k / n is the probability that each bit will be equal to one, then you should look at Bernoulli and Geometric distributions.