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

StackOverflow https://stackoverflow.com/questions/1851134

题

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

0111
1011
1101
1110

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

有帮助吗？

解决方案

此方法将生成具有恰好N '1' 比特的所有整数。

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

  

计算的字典顺序下一个比特置换

     

假设我们有一个整数设置为1的N位的模式，我们希望   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) GNU C编译器本征为x86处理器返回尾随零的数目。如果您使用的是Microsoft编译器   86，内在是_BitScanForward。这些都发出bsf   指令，但等同物可以是可用于其他体系结构。   如果没有，那么可以考虑使用的方法之一，用于计算   连续的零位前面提到的。这里是另一个版本   往往因为其除法运算的要慢一些，但它不   需要计数尾随零。

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

由于阿根廷的达里奥Sneidermanis，谁在2009年11月28日，提供了这个。

其他提示

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

说明：

本质上讲，我们需要选择1位的位置。有n选择全部N位中选择k位的k个办法。 itertools是一个很好的模块，这是否给我们。 itertools.combinations（范围（N）中，k）将选择从k比特[0，1，2，...，N-1]，然后它只是一个建筑物中给出的那些比特索引字符串的问题。

既然你不使用Python，看看在itertools.combinations伪代码在这里：

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

应该很容易在任何语言来实现。

忘掉实施（“被它的字符串做”显然是一个的实施的问题！） - 想想在算法，天啊......就像在，你的第一个TAG，男人！

什么你正在寻找的是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)

即，第一项是存在或不存在：如果存在的话，则有K-1向左走（从尾又名全丁冷杉），如果不存在，仍然ķ离开去

模式匹配像SML或哈斯克尔功能的语言可能是最能表达这个伪代码（程序性的，就像我的大爱的Python，实际上可以通过包括富太的功能，如itertools.combinations掩盖了问题太深，它做了所有你因此拼搏隐藏它从你！）。

什么是你最熟悉的，为了这个目的 - 计划，SML，哈斯克尔，...？我会很乐意为您翻译上面的伪代码。我能做到这一点的语言如Python也是如此，当然 - 但由于点越来越清楚地了解这个家庭作业机制，我也不会用，太丰富的功能，如itertools.combinations，而是递归（递归在剔除，如果需要的话）上更明显的原语（例如，头，尾，和串联）。但请不要让我们知道伪般的语言你最熟悉的！ （你明白，你的问题是状态相同等效于“得到的K个出或范围（N）的所有组合”，对吧？）。

此C＃方法返回创建所有组合的枚举器。因为它作为你枚举它们创建组合它只使用堆栈空间，所以它不是通过存储器空间，因为它可以创建组合的数量的限制。

这就是我想出的第一个版本。它是由堆栈空间限制到约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;
      }
    }
  }
}

这是第二个版本中，使用二进制分裂，而不是分割断的第一个字符，所以它更有效地使用该堆栈。它仅由对于它创建在每次迭代中字符串的内存空间的限制，并且我测试高达千万的长度：

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;
        }
      }
    }
  }
}

此问题的许多标准解决方案的一个问题是生成整组字符串，然后迭代这些字符串，这可能会耗尽堆栈。除了最小的集合之外，它很快就会变得难以使用。此外，在许多情况下，只需要部分采样，但标准（递归）解决方案通常将问题分成严重偏向一个方向的部分（例如，考虑所有具有零起始位的解决方案，然后考虑所有具有一起始位的解决方案）。

在许多情况下，更希望能够将位串（指定元素选择）传递给函数并让它以具有最小变化的方式返回下一个位串（这称为格雷）代码）并拥有所有元素的表示。

Donald Knuth 在他的 Fascicle 3A 第 7.2.1.3 节中介绍了这方面的一整套算法：生成所有组合。

对于从 n 处选择 k 元素的所有方式，有一种解决迭代格雷码算法的方法 http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl页面底部的注释（单击以展开）中列出了最终 PHP 代码的链接。

一个算法，该算法应工作：

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)

祝你好运！

在一个更通用的方法，下面的功能会给你所有可能的组合指数对于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

一种可能的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')])

..其中k是在1 "0111"s的数量。

itertools模块里说明了其方法的等同物;参见href="http://docs.python.org/library/itertools.html#itertools.permutations" rel="nofollow noreferrer">置换方法中

我想尝试递归。

有n个数字与他们1S中的k。查看此的另一种方式为k + 1个时隙。其中分布式n-k个0的序列。即，k倍（0后跟一个1游程），再其次是0的另一个运行。任何这些运行的可以是零长度的，但总长度需要N-K。

代表此为k + 1个的整数数组。转换为在递归的底部的字符串。

递归调用到深度n-k个，即递增递归调用前的数组的一个元素，然后递减它的方法中，k + 1次。

目前正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);
}

这已经有一段时间，因为我已经做了Java，所以有这个代码可能一些错误，但这个想法应该工作。

是字符串比整数数组快？前面加上为字符串的所有解决方案，可能导致在每次迭代的字符串的副本。

所以，可能是最有效的方法是int或char类型的数组，你追加。 Java有高效的可扩展的容器，对不对？使用，如果它比字符串快。或者，如果BigInteger的是有效率的，它肯定是紧凑的，因为每一位只需要多一点，而不是整个字节或INT。但随后遍历你需要与伪装了一下，位位移面具下一个位位置的位。所以可能比较慢，除非JIT编译所擅长的，这几天。

我会张贴此一个原始的问题中留言，但我的人缘不够高。遗憾。

的Python（功能样式）

使用python的itertools.combinations您可以生成k n我们的所有选择，而这些选择与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)]

用法示例：

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)]
不隶属于 StackOverflow
scroll top