optimization - n 组位的高效随机排列

Question

对于生成具有恰好 n 个设置位的位模式的问题，我知道两种实用的方法，但它们都有我不满意的局限性。

首先，您可以枚举在预先计算的表中设置了那么多位的所有可能的字值，然后在该表中生成一个随机索引以挑选出可能的结果。这存在一个问题，即随着输出大小的增长，候选输出列表最终会变得不切实际的大。

或者，您可以随机选择 n 个不重叠的位位置(例如，通过使用部分 Fisher-Yates 洗牌)并仅设置这些位。然而，这种方法在比可能结果的数量大得多的空间中计算随机状态。例如，它可以选择三位中的第一位和第二位，或者可以单独选择第二位和第一位。

第二种方法必须消耗比严格要求更多的随机数源位。由于它在顺序不重要时以特定顺序选择n位，这意味着它在产生相同结果的n!不同方式之间进行任意区分，并且消耗至少 floor(log_2(n!)) 多于所需的位数。

这种情况可以避免吗？

显然还有第三种方法，即迭代计算并计算合法排列，直到达到随机索引，但这只是第一种方法的空间与时间权衡，并且没有直接帮助，除非有是计算这些 n 排列的有效方法。

---

澄清

第一种方法需要选择一个介于 0 和 之间的随机数。 (其中 w 是输出大小)，因为这是可能的解决方案的数量。

第二种方法需要在零和w-1、零和w-2等之间选择n个随机值，这些有一个产品 ，即 比第一种方法大几倍。

这意味着随机数源被迫产生位来区分 n! 个不同的结果，这些结果都是等效的。我想知道是否有一种有效的方法来避免依赖这种多余的随机性。也许通过使用生成位位置无序列表的算法，或者直接计算第 n 个唯一的位排列。

Answer 1

似乎您想要弗洛伊德算法的变体:

Algorithm to select a single, random combination of values?

对于您的情况应该特别有用，因为遏制测试是一个简单的位掩码操作。这仅需要k次调用RNG。在下面的代码中，我假设您有 randint(limit)它从 0 产生一个均匀的随机数至limit-1 ，并且您希望在 32 位 int 中设置 k 位:

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并对结果求反。

如果您使用 colex 顺序而不是词典顺序，则生成代表集合中的一个组合的单个随机数(数学家将其称为组合的排名)的替代建议会更简单。这段代码例如:

for (i = k; i >= 1; --i) {
    while ((b = binomial(n, i)) > r) --n;
    buf[i-1] = n;
    r -= b;
}

将使用从 0 到 n-1 的索引填充数组 buf[]，用于 colex 等级 的 k 组合r。。在您的情况下，您将替换 buf[i-1] = n与 mask |= (1 << n) 。 binomial() 函数是二项式系数，我使用查找表执行此操作(请参阅 this )。这将最有效地利用熵，但我仍然认为弗洛伊德的算法将是更好的折衷方案。