伪随机数发生器，固定密度为1s [英] Pseudo Random Number generator with fixed density of 1s

问题描述

我正在寻找生成伪随机数的方法(可能具有较低的随机性")或 具有固定汉明权重[1s的固定密度]的伪随机比特序列. 我发现了一些建议，将简单的线性同余生成器与具有所需汉明权重的种子一起使用，但没有给出理由说明为什么这是正确的[为什么汉明权重在线性同余变换下不变]

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?

谢谢...

推荐答案

使用伪随机数生成器(PRNG)甚至是一个种子重量轻的简单生成器，绝对不是一个好的解决方案. PRNG不能使种子的汉明权重保持恒定，因此PRNG的整个思想是删除种子的信息.

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.

如果您希望将exacly位设置为n中的1，则您的问题是两个问题之间的k个非重复整数列表.如果k远小于n，则改组解为O(n).我认为以下解决方案是O(k).

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))

如果您想将大约k位设置为1，而k/n是每个位为1的概率，则必须查看Bernouilli和Geometric分布.

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.

这篇关于伪随机数发生器，固定密度为1s的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！