找到包含 k 位集合的所有长度为 n 的二进制字符串的最佳算法是什么?例如,如果 n=4 且 k=3,则有...
0111
1011
1101
1110
在给定任何 n 和任何 k 的情况下,我需要一种生成这些的好方法,所以我希望它用字符串来完成。
找到包含 k 位集合的所有长度为 n 的二进制字符串的最佳算法是什么?例如,如果 n=4 且 k=3,则有...
0111
1011
1101
1110
在给定任何 n 和任何 k 的情况下,我需要一种生成这些的好方法,所以我希望它用字符串来完成。
此方法将生成恰好具有 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 日提供了此信息。
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
应该很容易用任何语言实现。
忘记实现(“用字符串完成”显然是一个实现问题!)——考虑一下算法,看在皮特的份上……就像你的第一个标签一样,伙计!
您正在寻找的是一组 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)取出”相同,对吗?)。
此 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;
}
}
}
}
}
这个问题的许多标准解决方案的一个问题是生成了整组字符串,然后迭代这些字符串,这可能会耗尽堆栈。除了最小的集合之外,它很快就会变得笨拙。此外,在许多情况下,只需要部分采样,但标准(递归)解决方案通常将问题分成严重偏向一个方向的部分(例如,考虑所有起始位为零的解决方案,然后所有一个起始位的解决方案)。
在许多情况下,更希望能够将一个位串(指定元素选择)传递给一个函数,并让它返回下一个位串,以便具有最小的变化(这被称为灰色代码)并具有所有元素的表示。
Donald Knuth 在他的 Fascicle 3A 第 7.2.1.3 节:生成所有组合中涵盖了很多算法。
在http://answers.yahoo.com/question/index?qid=20081208224633AA0gdMl中,有一种方法可以解决从 n 中选择 k 个元素的所有方法的迭代格雷码算法, 并带有指向最终 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)
祝你好运!
一种可能的 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 模块解释了它的方法的等价物;请参阅置换方法的等效项。
以更通用的方式,以下函数将为您提供 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
我会尝试递归。
有 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 以来已经有一段时间了,所以这段代码中可能存在一些错误,但这个想法应该可行。
字符串比整数数组快吗?字符串前面的所有解决方案可能会在每次迭代时生成字符串的副本。
因此,最有效的方法可能是您附加到的 int 或 char 数组。Java 有高效的可增长容器,对吧?如果它比字符串快,请使用它。或者如果 BigInteger 是有效的,它肯定是紧凑的,因为每个位只需要一点,而不是整个字节或整数。但随后迭代您需要屏蔽位的位,并将掩码移位到下一个位位置。所以可能会更慢,除非 JIT 编译器现在很擅长。
我会在原始问题上发表评论,但我的业力还不够高。对不起。
使用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)]
好吧,对于这个问题(您需要按照设置位数量的递增顺序迭代所有子掩码),它已被标记为此问题的副本。
我们可以简单地遍历所有子掩码,将它们添加到一个向量中,并根据设置的位数对其进行排序。
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)