我是一名有用的助手，可以帮您进行文本翻译。
我有一个问题，不知道该如何解决。
我的问题是：我有一个二进制字符串，想生成所有可能的二进制子字符串。
例如：
input : 10111
output: 10000, 10100,00111,00001,10110 ...
我该如何快速而聪明地完成这项任务？
如何生成二进制字符串的所有可能子集？
3
我该如何快速而聪明地完成这项任务？
- mr.bio
6
1什么是“二进制字符串”？它是否包含ASCII形式的二进制数字，如0x30和0x31？您的示例未显示子字符串，而是某种排列或组合。请提供更多细节。 - Milan Babuškov
我指的是二进制字符串，例如 s = "1000001010001"，即只包含 0 和 1 的字符串 :) - mr.bio
mr.bio，您可能想了解一下子集的概念。如果某物不是一个集合，那么它就没有子集。如果我理解您的问题，我认为您所寻找的没有标准名称。也许可以称之为子掩码？ - Peter Alexander
如果您将值为1的位置集合视为一个集合问题，那么您可以将其解释为一个集合问题。 对于上面的示例，输入集将是（从右到左计数）：{0, 1, 2, 4}，输出将对应于子集{4}，{2, 4}，{0, 1, 2}，{0}，{1, 2, 4}（编辑：如果我能数清楚也会更好！）。 - Michael Petito
所有可能的二进制子串应该意味着：最大数量的唯一、非零二进制字符串，它们进行按位或运算后将得到“主”二进制字符串？ - Eugen Constantin Dinca
2顺便说一句，所有子集的集合就是幂集。因此，你实际上要生成的是二进制字符串中"set"位的幂集。 - Michael Petito
5个回答
6
Magic - 假定位掩码:
subset( int x )
list = ()
for ( int i = x; i >= 0; i = ( ( i - 1 ) & x ) )
list.append( i )
return list
您可以使用相同的逻辑，尽管这需要更多的操作，但可以应用于二进制字符串。
- Larry
2
不用在意——我忘了你的数据是字符串形式而不是整型/长整型等。不过你仍然可以使用相同的逻辑……只需按二进制计数，但仅使用包含1的位置。
只是随口一想。
我们来看看字符串1001。
我认为你想要的是四个数字：1001、1000、0001和0000，对吗？
如果是这样，你正在计算“1”的位置。
其中一种方法是存储原始数字。
orig = n;
然后开始对此进行迭代，并遍历每一个较小的数字。
while(n--)
但是，在每次迭代中，忽略试图将1放在0的位置的情况：
if(n & !orig)
continue;
如果您期望它是稀疏的——也就是说有很多零和很少的1，您可以使用一种移位机制。假设您的数字是1000 1001，注意到这里有三个1，对000到111进行计数，但是对于每次迭代，请再次展开位：
n & 0000 0001 | n << 2 & 0000 1000 | n << 5 & 1000 0000
或者换一种思考方式：
n & 001 | (n & 010) * 1000 | (n & 100) * 1000 000
由于它涉及到一个内部循环，对于原始数字中出现的每个1都需要进行一次迭代，因此根据1的数量不同，这可能比另一种解决方案慢。非常抱歉在二进制和十进制之间切换，如果您喜欢，我可以全部用十六进制表示。
目前我想不出直接映射位而不需要移位的模式——这将是最好的解决方案。
- Bill K
1
使用递归。
printsubsets(const string &in, const string &out)
{
if(in.empty())
{
cout<<out<<"\n";
return;
}
if(in[0]=='1')
printsubsets(in.substr(1), out+"1");
printsubsets(in.substr(1), out+"0");
}
- Eclipse
1
这就是它：
vector<string> submasks(string in)
{
vector<string> out;
out.push_back(string(in.size(), '0'));
for (int i = 0; i < in.size(); ++i)
{
if (in[i] == '0') continue;
int n = out.size();
for (int j = 0; j < n; ++j)
{
string s = out[j];
s[i] = '1';
out.push_back(s);
}
}
return out;
}
算法的步骤如下：
- 从只包含空位字符串 '00000...' 的向量开始。
- 对于输入字符串中的每个 1：创建一个在输出向量中将该位置设为 1 的字符串副本。
我认为这几乎是最优解了。
- Peter Alexander
0
1. 如果你只需要二进制字符串中小于某个数值的值，可以从二进制字符串中不断减去1，直到得到0。
2. 如果你想要用这些二进制位表示的所有值，则从能够用这些位数表示的最大数字中减去1，直到得到0。
这种类型的问题通常出现在那些编程挑战网站上。
这种类型的问题通常出现在那些编程挑战网站上。
- user183402
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接