翻转k个不同的二进制字符串的数量 [英] Number of different binary string with k flips
问题描述
我正在尝试一个问题，给我们一个长度为N(< 10 ^ 5)的二进制字符串，并且我们可以精确地以X(< 10 ^ 5)翻转，我们被问到有多少个不同的字符串可能的?我没有这个想法，我虽然可以使用dp解决它，但是不能递归.请帮助?
示例: 考虑N = 3，1 1 1和X = 2的二进制字符串 经过两次翻转后可以形成的新二进制字符串是 1 1 1(将第一位/第二位/第三位翻转两次) 0 0 1(第一和第二位翻转) 1 0 0(第二和第三位翻转) 0 1 0(第一和第三位翻转)
查找X翻转字符串
考虑例如N = 10，X = 4且初始字符串为
的情况 initial: 0011010111
这将是一个X翻转字符串的示例:
flipped: 0000111111
因为4位不同.如果对这两个字符串进行XOR，则会得到:
initial: 0011010111
flipped: 0000111111
XOR-ed: 0011101000
异或字符串中的4个设置位(1)表示已翻转的4个位的位置.
现在倒想一下.如果您有一个初始字符串和一个具有4个设置位的字符串，则可以通过对它们进行XOR运算来生成X翻转字符串:
initial: 0011010111
4 bits : 0011101000
XOR-ed: 0000111111
因此，如果您生成每个长度为N的带有X个置位的二进制字符串，并将它们与初始字符串进行XOR，则将获得所有X翻转的字符串.
initial 4 bits XOR-ed
0011010111 0000001111 0011011000
0000010111 0011000000
0000100111 0011110000
...
1110010000 1101000111
1110100000 1101110111
1111000000 1100010111
例如，可以用X个设置位生成所有N个长度的字符串.与闲聊" .在下面的代码示例中，我使用了反向字典顺序函数，该函数最初是为二项式系数 N choose X.当然，您还必须考虑到X-2，X-4，X-6 ...的字符串也发生了翻转，因此总数为:
(N选择X)+(N选择X-2)+(N选择X-4)+(N选择X-6)+ ... +(N选择(1或0))
如果X大于N，则根据X-N是偶数还是奇数，从N choose N或N choose N-1开始.
对于您的示例，其中N = 3和X = 2，总数为:
(3 choose 2) + (3 choose 0) = 3 + 1 = 4
对于上面的示例，其中N = 10，X = 4，总数为:
(10 choose 4) + (10 choose 2) + (10 choose 0) = 210 + 45 + 1 = 256
对于另一个答案中N = 6和X = 4的示例，正确的数字是:
(6 choose 4) + (6 choose 2) + (6 choose 0) = 15 + 15 + 1 = 31
示例代码
此JavaScript代码段按字典顺序反向生成二进制字符串序列(以便使设置的位从左向右移动)，然后打印出上述示例产生的翻转字符串和总数:
function flipBits(init, x) {
var n = init.length, bits = [], count = 0;
if (x > n) x = n - (x - n) % 2; // reduce x if it is greater than n
for (; x >= 0; x -= 2) { // x, x-2, x-4, ... down to 1 or 0
for (var i = 0; i < n; i++) bits[i] = i < x ? 1 : 0; // x ones, then zeros
do {++count;
var flip = XOR(init, bits);
document.write(init + " ⊕ " + bits + " → " + flip + "<br>");
} while (revLexi(bits));
}
return count;
function XOR(a, b) { // XOR's two binary arrays (because JavaScript)
var c = [];
for (var i = 0; i < a.length; i++) c[i] = a[i] ^ b[i];
return c;
}
function revLexi(seq) { // next string in reverse lexicographical order
var max = true, pos = seq.length, set = 1;
while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
if (pos < 0) return false;
seq[pos] = 0;
while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
return true;
}
}
document.write(flipBits([1,1,1], 2) + "<br>");
document.write(flipBits([0,0,1,1,0,1,0,1,1,1], 4) + "<br>");
document.write(flipBits([1,1,1,1,1,1], 4) + "<br>");
I am trying a problem where we are given binary string of length N(<10^5), and we are allowed exactly X(<10^5) flips on it, we are asked how many different string is possible? I am not getting idea about this, i though that it might be solved using dp, but not able to come with a recursion. Plz Help?
Example: consider the binary string of N = 3 , 1 1 1 , and X = 2 New Binary strings that can be formed after applying 2 flips are 1 1 1 (flipped the first/second/third bit twice) 0 0 1 (flipped first and second bit) 1 0 0 (flipped 2nd and 3rd bit) 0 1 0 (flipped 1st and 3rd bit)
Finding X-flipped strings
Consider e.g. the case where N=10, X=4 and the initial string is:
initial: 0011010111
then this would be an example of an X-flipped string:
flipped: 0000111111
because 4 bits are different. If you XOR the two strings, you get:
initial: 0011010111
flipped: 0000111111
XOR-ed: 0011101000
where the 4 set bits (ones) in the XOR-ed string indicate the location of the 4 bits which have been flipped.
Now think of this backwards. If you have an initial string, and a string with 4 set bits, then you can generate an X-flipped string by XOR-ing them:
initial: 0011010111
4 bits : 0011101000
XOR-ed: 0000111111
So if you generate every binary string of length N with X set bits, and you XOR these with the inital string, you get all the X-flipped strings.
initial 4 bits XOR-ed
0011010111 0000001111 0011011000
0000010111 0011000000
0000100111 0011110000
...
1110010000 1101000111
1110100000 1101110111
1111000000 1100010111
Generating all N-length strings with X set bits can be done e.g. with Gosper's Hack. In the code example below I use a reverse-lexicographical order function, which I originally wrote for this answer.
Double-flipping
If bits can be flipped twice, it is possible that the X-flipped string doesn't have X bits different from the initial string, but only X-2, because one bit was flipped and then flipped back to its original state. Or X-4, if the bit was flipped 4 times, or two different bits were flipped twice. In fact, the number of different bits could be X, X-2, X-4, X-6 ... down to 1 or 0 (depending on whether X is odd or even).
So, to generate all X-flipped strings, you generate all strings with X flipped bits, then all strings with X-2 flipped bits, then X-4, X-6 ... down to 1 or 0.
If X > N
If X is greater than N, then obviously some bits will be flipped more than once. The method to generate them is the same: you start at X, count down to X-2, X-4, X-6 ... but only generate strings for values ≤ N. So practically, you start at N or N-1, depending on whether X-N is even or odd.
Total number of strings
The number of N-length strings with X flipped bits equals the number of N-length strings with X set bits, which is the Binomial Coefficient N choose X. Of course you have to take into account the strings with X-2, X-4, X-6 ... flipped bits too, so the total is:
(N choose X) + (N choose X-2) + (N choose X-4) + (N choose X-6) + ... + (N choose (1 or 0))
In the case where X is greater than N, you start at N choose N or N choose N-1, depending on whether X-N is even or odd.
For your example with N=3 and X=2, the total number is:
(3 choose 2) + (3 choose 0) = 3 + 1 = 4
For the example above with N=10 and X=4, the total number is:
(10 choose 4) + (10 choose 2) + (10 choose 0) = 210 + 45 + 1 = 256
For the example in the other answer with N=6 and X=4, the correct number is:
(6 choose 4) + (6 choose 2) + (6 choose 0) = 15 + 15 + 1 = 31
Example code
This JavaScript code snippet generates the sequences of binary strings in reverse lexicographical order (so that the set bits move from left to right) and then prints out the resulting flipped strings and the total count for the examples described above:
function flipBits(init, x) {
var n = init.length, bits = [], count = 0;
if (x > n) x = n - (x - n) % 2; // reduce x if it is greater than n
for (; x >= 0; x -= 2) { // x, x-2, x-4, ... down to 1 or 0
for (var i = 0; i < n; i++) bits[i] = i < x ? 1 : 0; // x ones, then zeros
do {++count;
var flip = XOR(init, bits);
document.write(init + " ⊕ " + bits + " → " + flip + "<br>");
} while (revLexi(bits));
}
return count;
function XOR(a, b) { // XOR's two binary arrays (because JavaScript)
var c = [];
for (var i = 0; i < a.length; i++) c[i] = a[i] ^ b[i];
return c;
}
function revLexi(seq) { // next string in reverse lexicographical order
var max = true, pos = seq.length, set = 1;
while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
if (pos < 0) return false;
seq[pos] = 0;
while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
return true;
}
}
document.write(flipBits([1,1,1], 2) + "<br>");
document.write(flipBits([0,0,1,1,0,1,0,1,1,1], 4) + "<br>");
document.write(flipBits([1,1,1,1,1,1], 4) + "<br>");
这篇关于翻转k个不同的二进制字符串的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
