Number of different binary string with k flips

问题:

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)

回答1:

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 + " &oplus; " + bits + " &rarr; " + 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>");

回答2:

This is in c#. See if it 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