对于产生精确的位模式的问题n设置位，我知道两种实用的方法，但它们都有我不满意的局限性。
首先，您可以枚举在预先计算的表中设置了那么多位的所有可能的字值，然后在该表中生成一个随机索引以挑选出可能的结果。这样做的问题是，随着输出大小的增长，候选输出列表最终会变得不切实际的大。
或者，您可以选择n随机不重叠的位位置（例如，通过使用部分 Fisher-Yates 混洗）并仅设置这些位。然而，这种方法在比可能结果的数量大得多的空间中计算随机状态。例如，它可以选择三个比特中的第一位和第二位，或者它可以单独选择第二位和第一位。
第二种方法必须消耗比严格要求更多的随机数源位。既然是选择n当它们的顺序不重要时，按特定顺序排列位，这意味着它正在任意区分n!产生相同结果的不同方式，并且至少消耗floor(log_2(n!))比需要的更多位。
这可以避免吗？
显然还有第三种方法，即迭代计算并计算合法排列，直到达到随机索引，但这只是第一种方法的空间与时间权衡，除非存在有效的方法，否则没有直接帮助。计算这些的方法n排列。
澄清
The first approach requires picking a single random number between zero and (where
w is the output size), as this is the number of possible solutions.
The second approach requires picking n random values between zero and w-1, zero and w-2, etc., and these have a product of , which is
times larger than the first approach.
这意味着随机数源被迫产生位来区分n!不同的结果都是等价的。我想知道是否有一种有效的方法来避免依赖这种多余的随机性。也许通过使用产生位位置无序列表的算法，或者通过直接计算第 n 个唯一的位排列。
看来你想要弗洛伊德算法的变体：
选择单个随机值组合的算法？
在您的情况下应该特别有用，因为遏制测试是一个简单的位掩码操作。这将只需要k呼叫 RNG。在下面的代码中，我假设您有randint(limit)它产生一个均匀的随机数0 to limit-1，以及你想要的k32 位 int 中设置的位：
mask = 0;
for (j = 32 - k; j < 32; ++j) {
r = randint(j+1);
b = 1 << r;
if (mask & b) mask |= (1 << j);
else mask |= b;
}
这里需要多少位熵取决于如何randint()已实施。如果k> 16，设置为 32 -k并否定结果。
您的另一种建议是生成代表集合中一种组合的单个随机数（数学家将其称为rank如果您使用 colex 顺序而不是字典顺序，则更简单。这段代码，例如：
for (i = k; i >= 1; --i) {
while ((b = binomial(n, i)) > r) --n;
buf[i-1] = n;
r -= b;
}
将填充数组buf[]索引从 0 到n-1为了k-colex等级的组合r。在你的情况下，你会替换buf[i-1] = n with mask |= (1 << n)。 binomial() 函数是二项式系数，我使用查找表执行此操作（请参阅this）。这将最有效地利用熵，但我仍然认为弗洛伊德的算法将是更好的折衷方案。