algorithm - 生成所有长度为 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));

x86 CPU 固有的__builtin_ctz(v)GNU C 编译器返回尾随零的数量。如果您使用 Microsoft 的 x86 编译器，则内在函数是_BitScanForward. 它们都发出一条bsf 指令，但其他架构可能也有等效的指令。如果不是，则考虑使用前面提到的对连续零位进行计数的方法之一。这是另一个版本，由于其除法运算符而趋于较慢，但它不需要计算尾随零。

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

感谢阿根廷的 Dario Sneidermanis，他于 2009 年 11 月 28 日提供了此信息。

Answer 2

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(range(n), k) 将从 [0, 1, 2 ... n-1] 中选择 k 位，然后只需在给定这些位索引的情况下构建字符串即可。

由于您没有使用 Python，请在此处查看 itertools.combinations 的伪代码：

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

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

Answer 3

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

您正在寻找的是一组 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, all-but-first-of setN)

即，第一个项目要么存在要么不存在：如果存在，你还有 K-1 离开（从尾部也就是除了冷杉之外），如果不存在，还有 K 离开。

像 SML 或 Haskell 这样的模式匹配函数式语言可能是表达这种伪代码的最佳方式（过程式语言，比如我最爱的 Python，实际上可能通过包含过于丰富的功能来掩盖问题太深，itertools.combinations例如你，因此对你隐藏它！）。

为此，您最熟悉什么——Scheme、SML、Haskell，...？我很乐意为您翻译上述伪代码。当然，我也可以用 Python 之类的语言来做——但因为重点是让你了解这个家庭作业的机制，所以我不会使用过于丰富的功能，例如itertools.combinations，而是使用递归（和递归-消除，如果需要）在更明显的原语（例如头、尾和连接）上。但是请务必让我们知道您最熟悉的类似伪代码的语言！（您确实了解您所陈述的问题与“将 K 项的所有组合或范围（N）取出”相同，对吗？）。

Answer 4

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

这是第二个版本，它使用二进制拆分而不是拆分第一个字符，因此它更有效地使用堆栈。它仅受它在每次迭代中创建的字符串的内存空间的限制，我已经测试了它的长度为 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;
        }
      }
    }
  }
}

Answer 5

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

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

Donald Knuth 在他的 Fascicle 3A 第 7.2.1.3 节：生成所有组合中涵盖了很多算法。

在http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl中，有一种方法可以解决从 n 中选择 k 个元素的所有方法的迭代格雷码算法， 并带有指向最终 PHP 代码的链接（在评论中列出）（单击以展开它）在页面底部。

Answer 6

一种应该有效的算法：

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)

祝你好运！

Answer 7

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

.. 中sk的数量在哪里。1"0111"

itertools 模块解释了它的方法的等价物；请参阅置换方法的等效项。

Answer 8

以更通用的方式，以下函数将为您提供 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

Answer 9

我会尝试递归。

有 n 个数字，其中 k 个为 1。另一种查看方式是 k+1 个时隙序列，其中分布有 nk 个 0。也就是说，（一个 0 后跟一个 1）k 次，然后是另一个 0 的运行。这些运行中的任何一个都可以长度为零，但总长度需要为 nk。

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

递归调用深度 nk，该方法在递归调用之前递增数组的一个元素，然后将其递减 k+1 次。

在 nk 的深度，输出字符串。

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 以来已经有一段时间了，所以这段代码中可能存在一些错误，但这个想法应该可行。

Answer 10

字符串比整数数组快吗？字符串前面的所有解决方案可能会在每次迭代时生成字符串的副本。

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

我会在原始问题上发表评论，但我的业力还不够高。对不起。

Answer 11

Python（函数式）

使用python'sitertools.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)]

Answer 12

好吧，对于这个问题（您需要按照设置位数量的递增顺序迭代所有子掩码），它已被标记为此问题的副本。

我们可以简单地遍历所有子掩码，将它们添加到一个向量中，并根据设置的位数对其进行排序。

vector<int> v;
for(ll i=mask;i>0;i=(i-1)&mask)
    v.push_back(i);
auto cmp = [](const auto &a, const auto &b){
    return __builtin_popcountll(a) < __builtin_popcountll(b);
}
v.sort(v.begin(), v.end(), cmp);

另一种方法是迭代所有子掩码 N 次，如果在第 i 次迭代中设置的位数等于 i，则向向量添加一个数字。

两种方式的复杂度都是 O(n*2^n)