Number of different binary strings with k flips

Question

I am trying to solve a problem when we are given a binary string of length N (<10 ^ 5), and we are allowed to click on it X exactly (<10 ^ 5), we are asked how many different lines are possible? I do not understand about this, but although it can be resolved with dp, it cannot come with recursion. Help plz?

Example: consider a binary string N = 3, 1 1 1 and X = 2 New binary strings that can be formed after applying 2 flip 1 1 1 (double-click the first / second / third bit) 0 0 1 (flipped first and second bits ) 1 0 0 (inverted 2nd and 3rd bit) 0 1 0 (inverted 1st and 3rd bit)

Answer 1

Search for X-flipped strings

Consider, for example, the case when N = 10, X = 4, and the initial row:

initial: 0011010111 

then this will be an example of an inverted X line:

 flipped: 0000111111 

because 4 bits are different. If you XOR two lines, you will get:

 initial: 0011010111 flipped: 0000111111 XOR-ed: 0011101000 

where four bits (units) in the XOR-ed line indicate the location of the 4 bits that have been flipped.

Now think about it back. If you have an initial string and a string with four bits set, you can generate an X-flipped string using XOR-ing:

 initial: 0011010111 4 bits : 0011101000 XOR-ed: 0000111111 

So, if you generate every binary string of length N with X set bits, and you are XOR with an inline string, you get all the lines with X-flipped upside down.

 initial 4 bits XOR-ed 0011010111 0000001111 0011011000 0000010111 0011000000 0000100111 0011110000 ... 1110010000 1101000111 1110100000 1101110111 1111000000 1100010111 

Generation of all N-length strings using X bit-bits can be performed, for example. with gosper hack . In the code example below, I am using the reverse lexicographic order function that I originally wrote for this answer .

Double click

If the bits can be flipped twice, it is possible that the X-flipped string does not have X bits other than the original string, but only X-2, because one bit was flipped and then returned to its original state, Or X-4 if a bit was flipped 4 times or two different bits were flipped twice. In fact, the number of different bits can be X, X-2, X-4, X-6 ... up to 1 or 0 (depending on whether X is odd or even).

So, to generate all lines with X-flipped, you generate all lines with inverted bits of X, then all lines with inverted bits of X-2, then X-4, X-6 ... 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 for generating them is the same: you start with X, count to X-2, X-4, X-6 ... but only generate lines for & le; N. In practice, you start with N or N-1, depending on whether XN is even or odd.

Total row count

The number of N-length strings with inverted bits of X is equal to the number of N-length strings with bits of the X set, which is the Binomial coefficient N choose X Of course, you have to consider lines with X-2, X-4, X-6 ... inverted bits too, so the total:

(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 with N choose N or N choose N-1 , depending on whether XN is even or odd.

For your example with N = 3 and X = 2, the total is:

 (3 choose 2) + (3 choose 0) = 3 + 1 = 4 

In the above example with N = 10 and X = 4, the total number:

 (10 choose 4) + (10 choose 2) + (10 choose 0) = 210 + 45 + 1 = 256 

For example, in another answer with N = 6 and X = 4, the correct number is:

 (6 choose 4) + (6 choose 2) + (6 choose 0) = 15 + 15 + 1 = 31 

Code example

This piece of JavaScript code generates binary string sequences in reverse lexicographic order (so that the given bits move from left to right), and then prints the received expanded lines and the total 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 + " &oplus; " + bits + " &rarr; " + flip + "<br>"); } while (revLexi(bits)); } return count; function XOR(a, b) { // XOR 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>"); 

Answer 2

This is in C #. See if this helps.

 static class Program { static void Main(string[] args) { string bnryStr = "111111"; int x = 4; //here in this string merely the poistions of the binary string numbers are placed //if the binary string is "1111111", this fakeStr will hold "0123456" string fakeStr = String.Empty; for (int i = 0; i < bnryStr.Length; i++) { fakeStr += i.ToString(); } char[] arr = fakeStr.ToCharArray(); // gets all combinations of the input string altered in x ways IEnumerable<IEnumerable<char>> result = Combinations(arr, x); // this holds all the combinations of positions of the binary string at which flips will be made List<string> places = new List<string>(); foreach (IEnumerable<char> elements in result) { string str = string.Empty; foreach (var item in elements) { str += item; } places.Add(str); } List<string> results = GetFlippedCombos(bnryStr, places); Console.WriteLine("The number of all possible combinations are: " + results.Count); foreach (var item in results) { Console.WriteLine(item); } Console.Read(); } /// <summary> /// Gets a list of flipped strings /// </summary> /// <param name="bnryStr">binary string</param> /// <param name="placeList">List of strings containing positions of binary string at which flips will be made</param> /// <returns>list of all possible combinations of flipped strings</returns> private static List<string> GetFlippedCombos(string bnryStr, List<string> placeList) { List<string> rtrnList = new List<string>(); foreach (var item in placeList) { rtrnList.Add(Flip(bnryStr, item)); } return rtrnList; } /// <summary> /// Flips all the positions (specified in 'places') of a binary string from 1 to 0 or vice versa /// </summary> /// <param name="bnryStr">binary string</param> /// <param name="places">string holding the position values at which flips are made</param> /// <returns>a flipped string</returns> private static string Flip(string bnryStr, string places) { StringBuilder str = new StringBuilder(bnryStr); foreach (char place in places) { int i = int.Parse(place.ToString()); char ch = str[i]; str.Replace(ch, '0' == ch ? '1' : '0', i, 1); } return str.ToString(); } /// <summary> /// Gets all combinations of k items from a collection with n elements /// </summary> /// <param name="elements">collection having n elements</param> /// <param name="k">no of combinations</param> /// <returns>all possible combinations of k items chosen from n elements</returns> private static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k) { if (k == 0) { return new[] { new T[0] }; } else { IEnumerable<T> elements1 = elements as IList<T> ?? elements.ToList(); IEnumerable<IEnumerable<T>> enumerable = elements1.SelectMany((e, i) => { IEnumerable<T> enumerable1 = elements as IList<T> ?? elements1.ToList(); return enumerable1.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)); }); return enumerable; } } } Result: Binary String: 111111 No. of Flips: 4 The number of all possible combinations are: 15 000011 000101 000110 001001 001010 001100 010001 010010 010100 011000 100001 100010 100100 101000 110000