问具有k个翻转的不同二进制串的数量

EN

initial: 0011010111  

flipped: 0000111111  

initial: 0011010111  
flipped: 0000111111  
XOR-ed:  0011101000  

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

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

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

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

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

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>");

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