用k位集生成所有长度为n的二进制串。

What's the best algorithm to find all binary strings of length n that contain k bits set? For example, if n=4 and k=3, there are...

找到包含k位集的长度n的所有二进制串的最佳算法是什么?例如，如果n=4和k=3，那么…

0111
1011
1101
1110

I need a good way to generate these given any n and any k so I'd prefer it to be done with strings.

我需要一个好的方法来生成这些给定的n和k所以我希望用字符串来做。

11 个解决方案

#1

This method will generate all integers with exactly N '1' bits.

这个方法将生成所有的整数，正好是N '1'位。

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

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

Compute the lexicographically next bit permutation

Suppose we have a pattern of N bits set to 1 in an integer and we want the next permutation of N 1 bits in a lexicographical sense. For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 00010101, 00010110, 00011001, 00011010, 00011100, 00100011, and so forth. The following is a fast way to compute the next permutation.

假设我们有一个整数的N位的模式，我们想要一个字典式意义下的N 1位的排列。例如，如果N是3，位模式是00010011，下一个模式将是00010101,0001011011001,000110100001100,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));

The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros. If you are using Microsoft compilers for x86, the intrinsic is _BitScanForward. These both emit a bsf instruction, but equivalents may be available for other architectures. If not, then consider using one of the methods for counting the consecutive zero bits mentioned earlier. Here is another version that tends to be slower because of its division operator, but it does not require counting the trailing zeros.

x86 cpu的__builtin_ctz(v) GNU C编译器将返回尾随零的数量。如果您使用的是x86的Microsoft编译器，那么它的本质是_BitScanForward。这些都可以发出bsf指令，但其他架构可能也可以使用。如果没有，那么考虑使用前面提到的连续零位的方法之一。这里是另一个版本，由于它的除法运算符，它往往会比较慢，但是它不需要计算尾随零。

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

Thanks to Dario Sneidermanis of Argentina, who provided this on November 28, 2009.

感谢阿根廷的达里奥·斯内德曼尼斯，他于2009年11月28日提供了这一消息。

#2

Python

Python

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']

Explanation:

解释:

Essentially we need to choose the positions of the 1-bits. There are n choose k ways of choosing k bits among n total bits. itertools is a nice module that does this for us. itertools.combinations(range(n), k) will choose k bits from [0, 1, 2 ... n-1] and then it's just a matter of building the string given those bit indexes.

实际上，我们需要选择1位的位置。在n个总比特中有n个选择k位的方法。itertools是一个很好的模块，它为我们做这个。组合(range(n)， k)将从[0,1,2…n-1，然后这只是一个建立字符串的问题给定这些位索引。

Since you aren't using Python, look at the pseudo-code for itertools.combinations here:

既然您没有使用Python，请查看itertools的伪代码。

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

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

Should be easy to implement in any language.

在任何语言中都应该易于实现。

Here's a Java combination generator:

这是一个Java组合生成器:

http://www.merriampark.com/comb.htm

http://www.merriampark.com/comb.htm

#3

Forget about implementation ("be it done with strings" is obviously an implementation issue!) -- think about the algorithm, for Pete's sake... just as in, your very first TAG, man!

忘记实现(“用字符串完成”显然是一个实现问题!)——考虑一下算法，看在Pete的份上……就像，你的第一个标签，伙计!

What you're looking for is all combinations of K items out of a set of N (the indices, 0 to N-1 , of the set bits). That's obviously simplest to express recursively, e.g., pseudocode:

你要找的是所有K项的组合从一组N(指数，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)

i.e., the first item is either present or absent: if present, you have K-1 left to go (from the tail aka all-but-firs), if absent, still K left to go.

即。第一个项目要么是现在，要么是缺席:如果现在，你有K-1离开(从尾部，也就是所有的- - -firs)，如果缺席，仍然K离开。

Pattern-matching functional languages like SML or Haskell may be best to express this pseudocode (procedural ones, like my big love Python, may actually mask the problem too deeply by including too-rich functionality, such as itertools.combinations, which does all the hard work for you and therefore HIDES it from you!).

像SML或Haskell这样的模式匹配函数语言可能最好地表达这种伪代码(像我的大爱Python一样，过程性语言可能会通过包含太丰富的功能来掩盖问题，比如itertools.组合，它为您完成所有的困难工作，因此将它隐藏起来!)

What are you most familiar with, for this purpose -- Scheme, SML, Haskell, ...? I'll be happy to translate the above pseudocode for you. I can do it in languages such as Python too, of course -- but since the point is getting you to understand the mechanics for this homework assignment, I won't use too-rich functionality such as itertools.combinations, but rather recursion (and recursion-elimination, if needed) on more obvious primitives (such as head, tail, and concatenation). But please DO let us know what pseudocode-like language you're most familiar with! (You DO understand that the problem you state is identically equipotent to "get all combinations of K items out or range(N)", right?).

你最熟悉的是什么，这个目的——Scheme, SML, Haskell，…?我很乐意为您翻译上面的伪代码。我可以在Python等语言,当然,但因为重点是让你理解力学作业,我不会使用太富有itertools.combinations等功能,而是递归(recursion-elimination,如果需要)更明显的原语(如头部、尾部和连接)。但是请务必让我们知道您最熟悉的伪代码语言!(你会明白，你所面临的问题是相同的，“得到K项的所有组合或范围(N)”,对吧?)。

#4

This C# method returns an enumerator that creates all combinations. As it creates the combinations as you enumerate them it only uses stack space, so it's not limited by memory space in the number of combinations that it can create.

这个c#方法返回创建所有组合的枚举器。当你枚举它们时，它会创建组合，它只使用堆栈空间，所以它不受内存空间的限制，因为它可以创建多个组合。

This is the first version that I came up with. It's limited by the stack space to a length of about 2700:

这是我想到的第一个版本。它受堆栈空间限制，长度约为2700:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    if (length > bits) {
      foreach (string s in BinStrings(length - 1, bits)) {
        yield return "0" + s;
      }
    }
    if (bits > 0) {
      foreach (string s in BinStrings(length - 1, bits - 1)) {
        yield return "1" + s;
      }
    }
  }
}

This is the second version, that uses a binary split rather than splitting off the first character, so it uses the stack much more efficiently. It's only limited by the memory space for the string that it creates in each iteration, and I have tested it up to a length of 10000000:

这是第二个版本，使用二进制拆分，而不是拆分第一个字符，因此它更有效地使用堆栈。它只局限于它在每次迭代中创建的字符串的内存空间，我已经测试了它的长度为10000000:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    int first = length / 2;
    int last = length - first;
    int low = Math.Max(0, bits - last);
    int high = Math.Min(bits, first);
    for (int i = low; i <= high; i++) {
      foreach (string f in BinStrings(first, i)) {
        foreach (string l in BinStrings(last, bits - i)) {
          yield return f + l;
        }
      }
    }
  }
}

#5

One problem with many of the standard solutions to this problem is that the entire set of strings is generated and then those are iterated through, which may exhaust the stack. It quickly becomes unwieldy for any but the smallest sets. In addition, in many instances, only a partial sampling is needed, but the standard (recursive) solutions generally chop the problem into pieces that are heavily biased to one direction (eg. consider all the solutions with a zero starting bit, and then all the solutions with a one starting bit).

这个问题的许多标准解决方案的一个问题是，生成了整个字符串集，然后遍历这些字符串，这可能会耗尽堆栈。它很快就变得笨拙，除了最小的集合。此外，在许多情况下，只需要部分抽样，但是标准(递归)解决方案通常将问题分解成严重偏向一个方向的部分(如。考虑所有的解决方案，起始位为零，然后所有的解决方案都有一个起始位。

In many cases, it would be more desireable to be able to pass a bit string (specifying element selection) to a function and have it return the next bit string in such a way as to have a minimal change (this is known as a Gray Code) and to have a representation of all the elements.

在许多情况下,它会更吸引能够通过一个位串(指定元素选择)的函数,它返回下一个位串的方式有一个最小的变化(这被称为灰色代码),所有元素的表示。

Donald Knuth covers a whole host of algorithms for this in his Fascicle 3A, section 7.2.1.3: Generating all Combinations.

Donald Knuth在他的Fascicle 3A, 7.2.1.3:生成所有组合中包含了一整套算法。

There is an approach for tackling the iterative Gray Code algorithm for all ways of choosing k elements from n at http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl with a link to final PHP code listed in the comment (click to expand it) at the bottom of the page.

有一种方法可以解决从n中选择k元素的所有方法的迭代灰色代码算法。qid=20081208224633AA0gdMl，链接到最后的PHP代码(单击以展开它)在页面底部。

#6

One algorithm that should work:

一个应该工作的算法:

generate-strings(prefix, len, numBits) -> String:
    if (len == 0):
        print prefix
        return
    if (len == numBits):
        print prefix + (len x "1")
    generate-strings(prefix + "0", len-1, numBits)
    generate-strings(prefix + "1", len-1, numBits)

Good luck!

好运！

#7

In a more generic way, the below function will give you all possible index combinations for an N choose K problem which you can then apply to a string or whatever else:

在一个更一般的方法中，下面的函数会给出一个N选K问题的所有可能的指数组合，然后你可以应用到一个字符串或其他任何东西:

def generate_index_combinations(n, k):

    possible_combinations = []

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            possible_combinations.append(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)
    return possible_combinations

#8

One possible 1.5-liner:

一个可能的1.5线:

$ python -c 'import itertools; \
             print set([ n for n in itertools.permutations("0111", 4)])'

set([('1', '1', '1', '0'), ('0', '1', '1', '1'), ..., ('1', '0', '1', '1')])

.. where k is the number of 1s in "0111".

. .其中k是“0111”中的1s数。

The itertools module explains equivalents for its methods; see the equivalent for the permutation method.

itertools模块解释了它的方法的等价物;看一下置换法的等价性。

#9

I would try recursion.

我将尝试递归。

There are n digits with k of them 1s. Another way to view this is sequence of k+1 slots with n-k 0s distributed among them. That is, (a run of 0s followed by a 1) k times, then followed by another run of 0s. Any of these runs can be of length zero, but the total length needs to be n-k.

有n个数字和k个1。另一种方法是k+1个槽的序列在它们之间分布。也就是说，(0后面跟着1)k次，然后是另一个0。这些运行中的任何一个都可以是长度为0的，但是总长度需要是n-k。

Represent this as an array of k+1 integers. Convert to a string at the bottom of the recursion.

将其表示为k+1整数数组。在递归的底部转换为一个字符串。

Recursively call to depth n-k, a method that increments one element of the array before a recursive call and then decrements it, k+1 times.

递归调用depth n-k，这个方法在递归调用之前增加数组的一个元素，然后再递减它，k+1次。

At the depth of n-k, output the string.

在n-k的深度，输出字符串。

int[] run = new int[k+1];

void recur(int depth) {
    if(depth == 0){
        output();
        return;
    }

    for(int i = 0; i < k + 1; ++i){
        ++run[i];
        recur(depth - 1);
        --run[i];
    }

public static void main(string[] arrrgghhs) {
    recur(n - k);
}

It's been a while since I have done Java, so there are probably some errors in this code, but the idea should work.

我已经有一段时间没有使用Java了，所以在这段代码中可能会有一些错误，但是这个想法应该是可行的。

#10

Are strings faster than an array of ints? All the solutions prepending to strings probably result in a copy of the string at each iteration.

字符串是否比数组的速度快?所有的解决方案都可能在每次迭代中产生一个字符串的副本。

So probably the most efficient way would be an array of int or char that you append to. Java has efficient growable containers, right? Use that, if it's faster than string. Or if BigInteger is efficient, it's certainly compact, since each bit only takes a bit, not a whole byte or int. But then to iterate over the bits you need to & mask a bit, and bitshift the mask to the next bit position. So probably slower, unless JIT compilers are good at that these days.

所以最有效的方法可能是你附加到的int或char数组。Java有高效的可增长容器，对吗?使用它，如果它比字符串快。或者如果BigInteger是有效的，它肯定是紧凑的，因为每个位只需要一点，而不是一个整数字节或整数。但是，要迭代您需要的位和掩码位，并将掩码移到下位位置。所以可能要慢一些，除非JIT编译器现在很擅长。

I would post this a a comment on the original question, but my karma isn't high enough. Sorry.

我将发表这篇关于最初的问题的评论，但是我的业力不够高。对不起。

#11

Python (functional style)

Using python's itertools.combinations you can generate all choices of k our of n and map those choices to a binary array with reduce

使用python的itertools.组合，您可以生成k的所有选项，并将这些选项映射到一个具有reduce的二进制数组。

from itertools import combinations
from functools import reduce # not necessary in python 2.x

def k_bits_on(k,n):
       one_at = lambda v,i:v[:i]+[1]+v[i+1:]
       return [tuple(reduce(one_at,c,[0]*n)) for c in combinations(range(n),k)]

Example usage:

使用示例:

In [4]: k_bits_on(2,5)
Out[4]:
[(0, 0, 0, 1, 1),
 (0, 0, 1, 0, 1),
 (0, 0, 1, 1, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)]