这更像是一个难题而不是编码问题。我需要找到可以生成多少个满足某些约束的二进制数。输入是
(integer) Len - Number of digits in the binary number
(integer) x
(integer) y
二进制数必须使得从二进制数中取任意 x 个相邻数字应至少包含 y 个 1。
例如 -
长度 = 6，x = 3，y = 2
0 1 1 0 1 1 - 长度为 6，从中取任意 3 个相邻数字，将有 2 个 l
我在一次采访中向我提出了这个 C# 编码问题，我想不出任何算法来解决这个问题。不寻找代码（虽然它是受欢迎的），任何形式的帮助，指针表示赞赏
这个问题可以使用动态规划来解决。主要思想是根据最后 x-1 位和每个二进制数的长度对二进制数进行分组。如果将位序列附加到一个数字会产生一个满足约束的数字，那么将相同的位序列附加到同一组中的任何数字都会产生一个满足约束的数字。
例如，x = 4, y = 2。 01011 和 10011 都具有相同的最后 3 位 (011)。将 0 附加到它们中的每一个，得到 010110 和 100110，都满足约束。
这是伪代码：
mask = (1<<(x-1)) - 1
count[0][0] = 1
for(i = 0; i < Len-1; ++i) {
for(j = 0; j < 1<<i && j < 1<<(x-1); ++j) {
if(i<x-1 || count1Bit(j*2+1)>=y)
count[i+1][(j*2+1)&mask] += count[i][j];
if(i<x-1 || count1Bit(j*2)>=y)
count[i+1][(j*2)&mask] += count[i][j];
}
}
answer = 0
for(j = 0; j < 1<<i && j < 1<<(x-1); ++j)
answer += count[Len][j];
该算法假设 Len >= x。时间复杂度为 O(Len*2^x)。
编辑
该count1Bit(j)函数计算 的二进制表示中 1 的个数j。
该算法的唯一输入是Len, x, and y。它从一个空的二进制字符串开始[length 0, group 0]，并反复尝试追加 0 和 1，直到长度等于 Len。它还对每组中满足 1 位约束的二进制字符串的数量进行分组和计数。该算法的输出是answer，它是满足约束的二进制字符串（数字）的数量。
对于 group 中的二进制字符串[length i, group j]，将 0 附加到它会导致 group 中的二进制字符串[length i+1, group (j*2)%(2^(x-1))]；将 1 附加到它会导致 group 中的二进制字符串[length i+1, group (j*2+1)%(2^(x-1))]。
让是满足 1 位约束count[i,j]的组中二进制字符串的数量。如果的二进制表示中[length i, group j]至少有1 ，则将 0 附加到这些二进制字符串中的每一个后会产生一个二进制字符串，该组 也满足 1 位约束。因此，我们可以添加到. 附加1的情况类似。yj*2count[i,j][length i+1, group (j*2)%(2^(x-1))]count[i,j]count[i+1,(j*2)%(2^(x-1))]
上述算法中的条件i<x-1是在长度小于 x-1 时保持二进制字符串的增长。
使用 LEN = 6、X = 3 和 Y = 2 的示例...
为 X 位构建一个详尽的位模式生成器。一个简单的二进制计数器可以做到这一点。例如，如果 X = 3，则从 0 到 7 的计数器将生成长度为 3 的所有可能的位模式。
模式是：
000
001
010
011
100
101
110
111
在构建模式时验证邻接要求。拒绝任何不符合条件的模式。基本上，这归结为拒绝任何包含少于 2 个“1”位 (Y = 2) 的模式。该列表精简为：
011
101
110
111
对于修剪列表的每个成员，添加一个“1”位并重新测试前 X 位。如果通过邻接测试，则保留新模式。对“0”位执行相同操作。例如，此步骤进行如下：
1011 <== Keep
1101 <== Keep
1110 <== Keep
1111 <== Keep
0011 <== Reject
0101 <== Reject
0110 <== Keep
0111 <== Keep
留下：
1011
1101
1110
1111
0110
0111
现在重复这个过程，直到剪枝集为空或成员长度变为 LEN 位长。最后剩下的唯一模式是：
111011
111101
111110
111111
110110
110111
101101
101110
101111
011011
011101
011110
011111
数一数，你就完成了。
请注意，您只需要在每次迭代中测试前 X 位，因为所有后续模式都在前面的步骤中进行了验证。
考虑到输入值是可变的并且想要查看实际输出，我使用递归算法来确定给定长度的 0 和 1 的所有组合：
private static void BinaryNumberWithOnes(int n, int dump, int ones, string s = "")
{
if (n == 0)
{
if (BinaryWithoutDumpCountContainsnumberOfOnes(s, dump,ones))
Console.WriteLine(s);
return;
}
BinaryNumberWithOnes(n - 1, dump, ones, s + "0");
BinaryNumberWithOnes(n - 1, dump, ones, s + "1");
}
和BinaryWithoutDumpCountContainsnumberOfOnes来判断二进制数是否满足条件
private static bool BinaryWithoutDumpCountContainsnumberOfOnes(string binaryNumber, int dump, int ones)
{
int current = 0;
int count = binaryNumber.Length;
while(current +dump < count)
{
var fail = binaryNumber.Remove(current, dump).Replace("0", "").Length < ones;
if (fail)
{
return false;
}
current++;
}
return true;
}
调用 BinaryNumberWithOnes(6, 3, 2) 将输出所有匹配的二进制数
010011
011011
011111
100011
100101
100111
101011
101101
101111
110011
110101
110110
110111
111011
111101
111110
111111
我不确定我的答案，但这是我的观点。看看吧，
长度=4，
y=2。
我刚刚取出了两个模式，因为模式必须至少包含 y 的 1。
X 1 1 X
1×1×
X - 代表不关心
现在第一个表达式的计数是 2 1 1 2 =4
对于第二个表达式 1 2 1 2 =4
但是 2 模式在两者之间是共同的，所以减去 2 ..所以总共会有 6 对满足条件。
天真的方法是树递归算法。
我们的递归方法会慢慢地建立数字，例如，它会从 开始xxxxxx，返回调用1xxxxx和的总和，0xxxxx它本身将返回调用的总和，10除非x/y 条件不是对它通过调用自身构建的字符串感到满意，它不会沿着这条路径走，如果您处于终端条件（构建了正确长度的数字），则返回 1。（请注意，由于我们正在构建字符串从左到右，您不必检查整个字符串的 x/y，只需考虑新添加的数字！）110001
通过返回所有调用的总和，所有返回的 1 将汇集在一起并由初始调用返回，等于构造字符串的数量。
不知道这个时间复杂度的大 O 符号是什么，它可能和它一样糟糕，O(2^n)*O(checking x/y conditions)但在大多数情况下它会从树上剪掉很多分支。
更新：我的一个见解是，如果递归树的所有分支到目前为止具有相同的最后一位数字，则可以“合并” x，因为以后将对所有数字应用相同的检查，因此您不妨将它们加倍并保存很多工作。这现在需要显式地构建树而不是通过递归调用隐式地构建树，并且可能需要某种散列方案来检测分支何时具有相同x的结尾，但是对于大长度，它将提供巨大的加速。
我的方法是首先获取最小数量为 1 的所有二进制数，这很容易，您只需获取长度为 x 的二进制数的每个唯一排列和 y 1，然后循环每个唯一排列“Len”次。通过在每个可能的组合中翻转这些种子的 0 位，我们可以保证迭代所有符合标准的二进制数。
from itertools import permutations, cycle, combinations
def uniq(x):
d = {}
for i in x:
d[i]=1
return d.keys()
def findn( l, x, y ):
window = []
for i in xrange(y):
window.append(1)
for i in xrange(x-y):
window.append(0)
perms = uniq(permutations(window))
seeds=[]
for p in perms:
pr = cycle(p)
seeds.append([ pr.next() for i in xrange(l) ]) ###a seed is a binary number fitting the criteria with minimum 1 bits
bin_numbers=[]
for seed in seeds:
if seed in bin_numbers: continue
indexes = [ i for i, x in enumerate(seed) if x == 0] ### get indexes of 0 "bits"
exit = False
for i in xrange(len(indexes)+1):
if( exit ): break
for combo in combinations(indexes, i): ### combinatorically flipping the zero bits in the seed
new_num = seed[:]
for index in combo: new_num[index]+=1
if new_num in bin_numbers:
### if our new binary number has been seen before
### we can break out since we are doing a depth first traversal
exit=True
break
else:
bin_numbers.append(new_num)
print len(bin_numbers)
findn(6,3,2)
这种方法的增长绝对是指数级的，但我想我会分享我的方法，以防它帮助其他人获得较低复杂度的解决方案......
听起来像嵌套的 for 循环就可以了。伪代码（未测试）。
value = '0101010111110101010111' // change this line to format you would need
for (i = 0; i < (Len-x); i++) { // loop over value from left to right
kount = 0
for (j = i; j < (i+x); j++) { // count '1' bits in the next 'x' bits
kount += value[j] // add 0 or 1
if kount >= y then return success
}
}
return fail
包含至少 Y 1 位的长度为 X 的模式的数量是可数的。对于这种情况x == y，我们知道只有一种2^x可能的模式符合标准。对于较小的y我们需要总结具有多余1位的模式数量和具有精确y位的模式数量。
choose(n, k) = n! / k! (n - k)!
numPatterns(x, y) {
total = 0
for (int j = x; j >= y; j--)
total += choose(x, j)
return total
}
例如 ：
X = 4, Y = 4 : 1 pattern
X = 4, Y = 3 : 1 + 4 = 5 patterns
X = 4, Y = 2 : 1 + 4 + 6 = 11 patterns
X = 4, Y = 1 : 1 + 4 + 6 + 4 = 15 patterns
X = 4, Y = 0 : 1 + 4 + 6 + 4 + 1 = 16
(all possible patterns have at least 0 1 bits)
所以让我们成为符合标准的长度模式M的数量。现在，该长度模式是位的子集。子模式有“窗口”位置，也有可能的总模式。如果我们从我们的任何模式开始，我们知道将 a 附加到右侧并移动到下一个窗口将导致我们已知的模式之一。问题是，我们可以添加多少个模式，右移，并且仍然有一个有效的模式？XYXN(N - x + 1)2^NM1MM0M
由于我们要添加一个零，我们必须要么远离零，要么我们必须已经处于一个M我们有多余1位的地方。反过来，我们可以询问有多少M模式具有精确的Y位，并以 a 开头1。这与“多少个长度模式X-1有Y-1位”相同，我们知道如何回答：
shiftablePatternCount = M - choose(X-1, Y-1)
shiftablePatternCount所以从 M 个可能性开始，当我们向右滑动时，我们将增加。新窗口中的所有模式都在 的集合中M，现在有一些模式重复了。我们将移动多次以填充N，(N - X)每次将计数增加shiftablePatternCount，所以完整的答案应该是：
totalCountOfMatchingPatterns = M + (N - X)*shiftablePatternCount
我碰巧正在使用类似于您的问题的算法，试图找到一种改进它的方法，我找到了您的问题。所以我会分享
static int GetCount(int length, int oneBits){
int result = 0;
double count = Math.Pow(2, length);
for (int i = 1; i <= count - 1; i++)
{
string str = Convert.ToString(i, 2).PadLeft(length, '0');
if (str.ToCharArray().Count(c => c == '1') == oneBits)
{
result++;
}
}
return result;
}
我认为不是很有效，但很好的解决方案。
设置一些条件并引入简单的帮助变量。
L = 6, x = 3 , y = 2 introduce d = x - y = 1
条件：如果下一个数字假设值和前面x-1个元素值的列表有多个0位> d下一个数字具体值必须为1，否则添加两个1和0的括号作为具体值。
开始：检查（条件）=> 0,1 由于 0 计数检查中的总零数。
Empty => add 0 and 1
第 1 步：检查（条件）
0 (number of next value if 0 and previous x - 1 zeros > d(=1)) -> add 1 to sequence
1 -> add both 0,1 in two different branches
第2步：检查（条件）
01 -> add 1
10 -> add 1
11 -> add 0,1 in two different branches
第 3 步：
011 -> add 0,1 in two branches
101 -> add 1 (the next value if 0 and prev x-1 seq would be 010, so we prune and set only 1)
110 -> add 1
111 -> add 0,1
第4步：
0110 -> obviously 1
0111 -> both 0,1
1011 -> both 0,1
1101 -> 1
1110 -> 1
1111 -> 0,1
第 5 步：
01101 -> 1
01110 -> 1
01111 -> 0,1
10110 -> 1
10111 -> 0,1
11011 -> 0,1
11101 -> 1
11110 -> 1
11111 -> 0,1
第 6 步（完成）：
011011
011101
011110
011111
101101
101110
101111
110110
110111
111011
111101
111110
111111
现在数一数。我也测试了 L = 6、x = 4 和 y = 2，但考虑检查算法是否有特殊情况和扩展情况。
注意：我很确定一些具有处置理论基础的算法应该是我算法的一个真正巨大的改进。
因此，在一系列 Len 二进制数字中，您正在寻找一个包含 y 1 的 x 长段。
见执行：http: //ideone.com/xuaWaK
这是我的Java算法：
import java.util.*;
import java.lang.*;
class Main
{
public static ArrayList<String> solve (String input, int x, int y)
{
int s = 0;
ArrayList<String> matches = new ArrayList<String>();
String segment = null;
for (int i=0; i<(input.length()-x); i++)
{
s = 0;
segment = input.substring(i,(i+x));
System.out.print(" i: "+i+" ");
for (char c : segment.toCharArray())
{
System.out.print("*");
if (c == '1')
{
s = s + 1;
}
}
if (s == y)
{
matches.add(segment);
}
System.out.println();
}
return matches;
}
public static void main (String [] args)
{
String input = "011010101001101110110110101010111011010101000110010";
int x = 6;
int y = 4;
ArrayList<String> matches = null;
matches = solve (input, x, y);
for (String match : matches)
{
System.out.println(" > "+match);
}
System.out.println(" Number of matches is " + matches.size());
}
}