生成所有设置了k位的长度为n的二进制string
find包含k位集的长度为n的所有二进制string的最佳algorithm是什么？ 例如，如果n = 4，k = 3，则有…
0111 1011 1101 1110 我需要一个好的方法来生成这些给定的任何n和任何k，所以我宁愿用string来完成。
该方法将生成具有N'1'位的所有整数。
从https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
计算字典顺序的下一位置换
假设我们有一个N位的模式被设置为1，我们希望N 1位的下一个排列在词典意义上。 例如，如果N是3并且位模式是
00010011，则下一个模式将是00010101等等。 以下是计算下一个排列的快速方法。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编译器返回尾随零的数量。 如果您正在使用x86的Microsoft编译器，则内部函数是_BitScanForward。 这些都发出bsf指令，但其他架构可用等价物。 如果不是，则考虑使用前面提到的连续的零位计数方法之一。 这里是另一个版本，由于它的除法运算符往往比较慢，但是不需要计算结尾的零。unsigned int t = (v | (v - 1)) + 1; w = t | ((((t & -t) / (v & -v)) >> 1) - 1);感谢阿根廷的Dario 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']
说明：
本质上我们需要select1位的位置。 有n个selectk个方法来select总共n个比特中的k个比特。 itertools是一个很好的模块，为我们做这个。 itertools.combinations（range（n），k）将从[0,1,2 … n-1]中selectk个位，然后只要给定这些位索引就可以构buildstring。
由于您没有使用Python，请在这里查看itertools.combinations的伪代码：
http://docs.python.org/library/itertools.html#itertools.combinations
应该很容易用任何语言来实现。
这是一个Java组合生成器：
忘记实现（“用string来完成”显然是一个实现问题！） – 考虑一下algorithm ，对皮特来说…就像你的第一个标签，人！
你正在寻找的是K个项目中的所有N个组合的集合（这些集合中的索引0到N-1）。 recursionexpression显然是最简单的，例如伪代码：
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这样的模式匹配函数语言可能是expression这种伪代码的最好方式（像我的大爱Python一样，程序性语言可能实际上通过包含过多的function掩盖了这个问题，比如itertools.combinations ，为你而努力工作，因此从你这里隐藏！）。
你最熟悉的是什么，为什么 – Scheme，SML，Haskell，…？ 我很乐意为你翻译上面的伪代码。 当然，我也可以用Python等语言来完成它 – 但是，由于重点在于让你了解这个家庭作业的机制，所以我不会使用像itertools.combinations这样的过于丰富的function，而是recursion（和recursion消除，如果需要的话）更加明显的原语（比如头，尾和串联）。 但是，请让我们知道您最熟悉的伪代码语言！ （你知道你说的这个问题和“把所有K个项目的组合或者范围（N）”等同起来，对吧？）。
这个C＃方法返回一个创build所有组合的枚举器。 由于它在枚举时创build了组合，因此它只使用堆栈空间，所以它不会受限于可以创build的组合的内存空间。
这是我想出的第一个版本。 它的堆栈空间限制在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; } } } }
这是第二个版本，它使用二进制拆分而不是分离第一个字符，所以它更有效地使用堆栈。 它只受到它在每次迭代中创build的string的内存空间的限制，我已经testing了它的长度为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; } } } } }
这个问题的许多标准解决scheme的一个问题是，整个string集合被生成，然后迭代通过，这可能耗尽堆栈。 除了最小的集合之外，它很快变得笨重。 此外，在很多情况下，只需要部分采样，但标准（recursion）解决scheme通常会将问题分解为严重偏向一个方向的问题（例如，考虑所有解决scheme的起始位为零，然后全部有一个开始位的解决scheme）。
在许多情况下，能够将一个位串（指定元素select）传递给一个函数并使其返回下一个位串以使得具有最小的改变（这被称为灰色代码）并具有所有元素的表示。
Donald Knuth在他的Fascicle 3A，第7.2.1.3节：生成所有组合中涵盖了大量的algorithm。
在http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl中; ，有一种方法可以解决迭代格雷码algorithm的所有selectk元素的方法，并链接到注释中列出的最终PHP代码点击展开它）在页面的底部。
一个应该工作的algorithm：
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)
祝你好运！
用更通用的方法，下面的函数将为您提供NselectK问题的所有可能的索引组合，然后您可以将其应用于string或其他任何内容：
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.5class轮：
$ 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是"0111"中1的个数。
itertools模块解释了其方法的等价物; 请参阅排列方法的等效项。
我会尝试recursion。
有n个数字，其中k是1。 另一种观察这种情况的方法是在其中分布nk个0的k + 1个时隙的序列。 也就是说，（运行0秒后1）k次，然后再运行0次。 任何这些运行可以是长度为零，但总长度需要为nk。
将其表示为k + 1个整数的数组。 转换为recursion底部的string。
recursion调用深度nk，在recursion调用之前递增数组中的一个元素，然后递减它，k + 1次。
在nk的深度，输出string。
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已经有一段时间了，所以在这段代码中可能有一些错误，但是这个想法应该是可行的。
string比int数组更快吗？ 所有预先考虑string的解决scheme可能会导致在每次迭代时string的副本。
所以可能最有效的方法是你追加的int或char数组。 Java有高效的可扩展容器，对吧？ 使用它，如果它比string更快。 或者，如果BigInteger是有效的，它确实是紧凑的，因为每一位只需要一点，而不是整个字节或整数。 但是，然后遍历你需要掩盖一点，并移位掩码到下一个位的位。 所以可能会慢一些，除非JIT编译器这些日子好。
我会发表这个原始问题的评论，但我的业力不够高。 抱歉。
Python（function风格）
使用python的itertools.combinations你可以生成所有的select，我们的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)]
