algorithm - 以随机顺序迭代具有相同数量的一(或零)的二进制数

Question

我需要以随机顺序生成具有相同数量的1（或0）的二进制数。
有谁知道固定长度二进制数的任何有效算法？
2位和4位数字的示例（为更加清楚起见）：

1100
1010
1001
0110
0101
0011

更新
无重复的随机顺序很重要。需要二进制数序列，而不是单个排列。

Answer 1

如果您有足够的内存来存储所有可能的位序列，并且您不介意在获得第一个结果之前就全部生成它们，那么解决方案是使用一些高效的生成器将所有可能的序列生成向量，然后进行随机播放使用Fisher-Yates随机播放向量。这很容易且没有偏见（只要您使用良好的随机数生成器进行随机播放），但是如果n很大，它可能会占用大量内存，特别是如果您不确定是否需要完成迭代时。

但是有两种解决方案不需要将所有可能的单词都保留在内存中。 （两种解决方案的C实现均紧随其后。）

1.洗牌一个枚举

最快的一种方法（我认为）是先生成一个随机的位值改组，然后一次遍历所有可能的单词，然后将改组应用于每个值的位。为了避免改组实际位的复杂性，可以以格雷码顺序生成字，其中只有两个位的位置从一个字变为下一个字。 （这也称为“旋转门”迭代，因为在添加每个新的1时，必须删除其他一些1。）这允许快速更新位掩码，但是这意味着要连续输入高度相关，可能不适用于某些目的。而且，对于n的较小值，可能的位混洗的数量非常有限，因此不会产生很多不同的序列。 （例如，对于n为4且k为2的情况，有6个可能的单词可以用6！（720）种不同的方式进行排序，但只有4！（24）个位洗牌可以通过在序列中的任意位置开始迭代来稍微改善。）

总是可以找到格雷码。这是一个n = 6，k = 3的示例：（每一步都交换粗体。我想在其下划线，但出于某些莫名其妙的原因，SO允许删除线而不是下划线。）

111000   010110   100011   010101
101100   001110   010011   001101
011100   101010   001011   101001
110100   011010   000111   011001
100110   110010   100101   110001

该序列可以由类似于 that suggested by @JasonBoubin的递归算法生成-唯一的区别是每个递归的后半部分需要以相反的顺序生成-但是使用非递归版本的算法很方便。下面的示例代码中的一个来自 Frank Ruskey's unpublished manuscript on Combinatorial Generation（第130页的算法5.7）。我对其进行了修改，以使用基于0的索引，并添加了代码以跟踪二进制表示形式。

2.随机生成一个整数序列并将其转换为组合

“更多”随机但稍微慢一些的解决方案是生成一个随机排列的枚举索引列表（在 [0, n choose k)中是顺序整数），然后找到与每个索引对应的单词。

产生连续范围内的随机整数列表的最简单的伪随机方法是使用随机选择的线性同余生成器（LCG）。 LCG是递归序列 xi = (a * xi-1 + c) mod m。如果 m为2的幂，则 a mod 4为1且 c mod 2为1，则该递归将循环遍历所有2m个可能的值。要遍历范围 [0, n choose k)，我们只需选择 m作为下一个2的大幂，然后跳过任何不在所需范围内的值。 （出于明显的原因，该值将小于所产生值的一半。）

要将枚举索引转换为实际单词，我们基于 n choose k单词集由以0开头的 n-1 choose k单词和以1开头的 n-1 choose k-1单词组成的事实对索引进行二项式分解。因此，产生第i个词：


如果 i < n-1 choose k我们输出一个0，然后输出n个1个位字的集合中的第k个字；
否则，我们输出1，然后从i中减去 n-1 choose k作为索引，将k-1位设置为n-1位字的集合。


预先计算所有有用的二项式系数很方便。

LCG的缺点是，在看到前几个术语后，它们很容易预测。同样， a和 c的一些随机选择的值将产生索引序列，其中连续索引高度相关。 （此外，低阶位始终是非随机的。）通过对最终结果也应用随机位改组，可以稍微缓解某些问题。下面的代码中没有对此进行说明，但是它将使速度减慢很少，并且应该很明显地做到这一点。 （它基本上是用对随机混排的表的查找代替 1UL<<n）。

下面的C代码使用了一些优化，使其难以阅读。二项式系数存储在下对角线数组中：

  row
index
 [ 0]   1
 [ 1]   1 1
 [ 3]   1 2 1
 [ 6]   1 3 3 1
 [10]   1 4 6 4 1

可以看出， binom(n, k)的数组索引是 n(n+1)/2 + k，如果有该索引，我们可以通过简单地减去 binom(n-1, k)来找到 n，而通过减去 binom(n-1, k-1)可以找到 n+1。为了避免需要在数组中存储零，我们确保不要在 k为负或大于 n的情况下查找二项式系数。特别是，如果我们到达了 k == n或 k == 0的递归点，我们肯定可以知道要查找的索引是0，因为只有一个可能的单词。此外，在带有某些 n和 k的单词集中的索引0
将精确地由 n-k零和后跟 k的1组成，这是2k-1的n位二进制表示。通过在索引达到0时简化算法，我们可以避免担心 binom(n-1, k)或 binom(n-1, k-1)之一不是有效索引的情况。

两种解决方案的C代码

带有乱序位的格雷码

void gray_combs(int n, int k) {
  /* bit[i] is the ith shuffled bit */
  uint32_t bit[n+1];
  {
    uint32_t mask = 1;
    for (int i = 0; i < n; ++i, mask <<= 1)
      bit[i] = mask;
    bit[n] = 0;
    shuffle(bit, n);
  }

  /* comb[i] for 0 <= i < k is the index of the ith bit
   * in the current combination. comb[k] is a sentinel. */
  int comb[k + 1];
  for (int i = 0; i < k; ++i) comb[i] = i;
  comb[k] = n;

  /* Initial word has the first k (shuffled) bits set */
  uint32_t word = 0;
  for (int i = 0; i < k; ++i) word |= bit[i];

  /* Now iterate over all combinations */
  int j = k - 1; /* See Ruskey for meaning of j */
  do {
    handle(word, n);
    if (j < 0) {
      word ^= bit[comb[0]] | bit[comb[0] - 1];
      if (--comb[0] == 0) j += 2;
    }
    else if (comb[j + 1] == comb[j] + 1) {
      word ^= bit[comb[j + 1]] | bit[j];
      comb[j + 1] = comb[j]; comb[j] = j;
      if (comb[j + 1] == comb[j] + 1) j += 2;
    }
    else if (j > 0) {
      word ^= bit[comb[j - 1]] | bit[comb[j] + 1];
      comb[j - 1] = comb[j]; ++comb[j];
      j -= 2;
    }
    else {
      word ^= bit[comb[j]] | bit[comb[j] + 1];
      ++comb[j];
    }
  } while (comb[k] == n);
}

具有枚举索引到单词转换的LCG

static const uint32_t* binom(unsigned n, unsigned k) {
  static const uint32_t b[] = {
    1,
    1, 1,
    1, 2, 1,
    1, 3, 3, 1,
    1, 4, 6, 4, 1,
    1, 5, 10, 10, 5, 1,
    1, 6, 15, 20, 15, 6, 1,
    // ... elided for space
  };
  return &b[n * (n + 1) / 2 + k];
}

static uint32_t enumerate(const uint32_t* b, uint32_t r, unsigned n, unsigned k) {
  uint32_t rv = 0;
  while (r) {
    do {
      b -= n;
      --n;
    } while (r < *b);
    r -= *b;
    --b;
    --k;
    rv |= 1UL << n;
  }
  return rv + (1UL << k) - 1;
}

static bool lcg_combs(unsigned n, unsigned k) {
  const uint32_t* b = binom(n, k);
  uint32_t count = *b;
  uint32_t m = 1; while (m < count) m <<= 1;
  uint32_t a = 4 * randrange(1, m / 4) + 1;
  uint32_t c = 2 * randrange(0, m / 2) + 1;
  uint32_t x = randrange(0, m);
  while (count--) {
    do
      x = (a * x + c) & (m - 1);
    while (x >= *b);
    handle(enumerate(b, x, n, k), n);
  }
  return true;
}

注意：我没有包括 randrange或 shuffle的实现；代码很容易获得。 randrange(low, lim)产生一个在 [low, lim)范围内的随机整数； shuffle(vec, n)随机混洗长度为 vec的整数矢量 n。

同样，循环为每个生成的单词调用 handle(word, n)。必须用每种组合所要做的任何事情来代替。

将 handle定义为不执行任何操作的函数， gray_combs用了150毫秒在我的笔记本电脑上查找了所有40,116,600个设置了14位的28位字。 lcg_combs用了5.5秒。