以随机顺序迭代具有相同数量的1(或0)的二进制数

Question

我需要以随机顺序生成具有相同数量的1(或0)的二进制数.
有谁知道固定长度二进制数的任何有效算法？2个1位和4位数的示例(只是为了更清楚):

1100
1010
1001
0110
0101
0011

更新无 重复的随机顺序非常重要.需要二进制数的序列,而不是单个排列.

Answer 1

如果你有足够的内存来存储所有可能的位序列,并且你不介意在得到第一个结果之前生成它们,那么解决方案就是使用一些有效的生成器将所有可能的序列生成到一个向量中然后随机播放使用Fisher-Yates shuffle的向量.这很容易且没有偏见(只要你使用一个好的随机数生成器来进行随机播放)但是如果n它很大,它可以使用大量内存,特别是如果你不确定你需要完成迭代.

但是有一些解决方案不需要在内存中保留所有可能的单词.(两种解决方案的C实现遵循文本.)

1.比特改变一个枚举

最快的(我认为)是首先生成随机的比特值,然后一次一个地迭代可能的单词,将shuffle应用于每个值的位.为了避免混淆实际比特的复杂化,可以以格雷码顺序生成字,其中只有两个比特位置从一个字改变到下一个字.(这也称为"旋转门"迭代,因为当1添加每个新的时,1必须删除其他一些.)这允许快速更新位掩码,但这意味着连续的条目高度相关,这可能是不适合某些目的.而且,对于n可能的比特混洗的数量的小值非常有限,因此不会产生很多不同的序列.(例如,对于n4和k2的情况,有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

这个序列可以通过类似于@JasonBoubin建议的递归算法生成 - 唯一的区别是每个递归的后半部分需要以相反的顺序生成 - 但是使用非递归版本的方法很方便.算法.以下示例代码中的一个来自Frank Ruskey关于组合生成的未发表的手稿(第130页的算法5.7).我将其修改为使用基于0的索引,以及添加代码以跟踪二进制表示.

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

"更多"随机但稍慢的解决方案是生成一个混合的枚举索引列表(它是连续的整数[0, n choose k)),然后找到对应于每个索引的单词.

在连续范围内产生混洗的整数列表的最简单的伪随机方法是使用随机选择的线性同余生成器(LCG).LCG是递归序列.如果是2的幂,是1并且是1,那么该递归将循环通过所有2 ^m个可能的值.要在范围内循环,我们只需选择下一个较大的2的幂,然后跳过任何不在所需范围内的值.(由于显而易见的原因,这个数值不到一半.)xi = (a * xi-1 + c) mod mma mod 4c mod 2[0, n choose k)m

为了将枚举索引转换为实际的单词,我们基于以下事实执行索引的二项式分解:n choose k单词组由n-1 choose k以0 n-1 choose k-1开头的单词和以1 开头的单词组成.因此,要生成第i ^个单词:

• 如果i < n-1 choose k我们输出一个0然后输出n位1 ^个字的第i ^个字,并设置k位;
• 否则,我们输出1然后n-1 choose k从i 减去作为索引到n-1比特字的集合中,设置k-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)is 的数组索引n(n+1)/2 + k,如果我们有那个索引,我们可以binom(n-1, k)通过简单地减去n和binom(n-1, k-1)减去来找到n+1.为了避免需要在数组中存储零,我们确保我们从不查找二项式系数,其中k负数或大于n.特别是,如果我们已经到达递归中的一个点k == n或者k == 0,我们肯定知道要查找的索引是0,因为只有一个可能的单词.另外,索引为0的组的一些单词n和k 将精确地包括n-k零,接着k的,它是2的n位二进制表示^ķ -1.通过在索引达到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毫秒找到与集合14位全部40116600 28位字.lcg_combs花了5.5秒.