生成长度为n且设置了k位的所有二进制字符串

Question

查找包含k位的所有长度为n的二进制字符串的最佳算法是什么？例如,如果n = 4且k = 3,则有......

0111
1011
1101
1110

我需要一个很好的方法来生成这些给定任何n和任何k所以我更喜欢用字符串来完成它.

Answer 1

此方法将生成具有正好N'1'位的所有整数.

来自https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

按字典顺序计算下一位排列

假设我们在整数中有一个N位设置为1的模式,我们希望在字典意义上下一个N 1位的排列.例如,如果N是3和位模式是00010011,下一个模式是00010101,00010110,00011001,00011010,00011100,00100011,等等.以下是计算下一个排列的快速方法.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

__builtin_ctz(v)x86 CPU 的GNU C编译器内部函数返回尾随零的数量.如果你使用的是x86的Microsoft编译器,那么内在的就是_BitScanForward.这些都发出bsf 指令,但是其他架构可以使用等价物.如果不是,则考虑使用其中一种方法来计算前面提到的连续零位.这是另一个版本,由于它的除法运算符而往往较慢,但它不需要计算尾随零.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

感谢阿根廷的Dario Sneidermanis,他于2009年11月28日提供了此服务.

Answer 2

蟒蛇

import itertools

def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result

print kbits(4, 3)

Output: ['1110', '1101', '1011', '0111']

说明:

基本上我们需要选择1位的位置.有n个选择k种方式在n个总位中选择k个比特.itertools是一个很好的模块,它为我们这样做.itertools.combinations(range(n),k)将从[0,1,2 ... n-1]中选择k位,然后只需在给定这些位索引的情况下构建字符串.

由于您不使用Python,请在此处查看itertools.combinations的伪代码:

http://docs.python.org/library/itertools.html#itertools.combinations

应该易于用任何语言实现.

Answer 3

忘掉实现("用字符串完成"显然是一个实现问题!) - 想想算法,为了Pete的缘故......就像在你的第一个TAG中一样!

你要找的是一组N中的K项的所有组合(指数,0到N-1,设置位).这显然是递归表达最简单的,例如伪代码:

combinations(K, setN):
  if k > length(setN): return "no combinations possible"
  if k == 0: return "empty combination"
  # combinations INcluding the first item:
  return (first-item-of setN) combined combinations(K-1, all-but-first-of setN)
   union combinations(K-1, all-but-first-of setN)

也就是说,第一个项目是存在还是不存在:如果存在,你有K-1离开(从尾部也称为全冷却),如果不存在,仍然K离开去.

像SML或Haskell这样的模式匹配函数语言可能最能表达这种伪代码(程序性的,就像我的大爱Python一样,实际上可能通过包含过于丰富的功能来过度掩盖问题,例如itertools.combinations,这样可以完成所有艰苦工作你并因此向你隐瞒它!).

为此,你最熟悉的是什么 - Scheme,SML,Haskell,......？我很乐意为你翻译上面的伪代码.当然,我也可以用Python这样的语言来做 - 但是由于重点是让你理解这个家庭作业的机制,我不会使用过于丰富的功能itertools.combinations,而是递归(和递归 -消除(如果需要)更明显的原语(例如头部,尾部和连接).但请让我们知道您最熟悉的伪代码语言!(您应该明白,您声明的问题与"获取K项目的所有组合或范围(N)"完全相同,对吧？).