Nombre de chaînes binaires différentes avec k flips

Question

J'essaie de résoudre un problème où l'on nous donne une chaîne binaire de longueur N(<10^5), et où l'on nous permet exactement X(<10^5) retournements sur cette chaîne, on nous demande combien de chaînes différentes sont possibles ? Je n'ai pas d'idée à ce sujet, je pensais qu'il pourrait être résolu en utilisant dp, mais je ne suis pas en mesure de venir avec une récursion. Aidez-moi, s'il vous plaît.

Exemple : Considérons la chaîne binaire de N = 3 , 1 1 1 , et X = 2. Les nouvelles chaînes binaires qui peuvent être formées après avoir appliqué 2 retournements sont les suivantes 1 1 1 (on retourne deux fois le premier, le deuxième et le troisième bit) 0 0 1 (retournement du premier et du deuxième bit) 1 0 0 (retournement des deuxième et troisième bits) 0 1 0 (retournement des 1er et 3e bits)

Answer 1

Trouver des chaînes de caractères retournées en X

Considérons par exemple le cas où N=10, X=4 et la chaîne initiale est :

initial: 0011010111  

alors ce serait un exemple de chaîne inversée :

flipped: 0000111111  

car 4 bits sont différents. Si on fait un XOR des deux chaînes, on obtient :

initial: 0011010111  
flipped: 0000111111  
XOR-ed:  0011101000  

où les 4 bits positionnés (uns) dans la chaîne XOR-ed indiquent l'emplacement des 4 bits qui ont été retournés.

Maintenant, pensez-y à l'envers. Si vous disposez d'une chaîne initiale et d'une chaîne avec 4 bits définis, vous pouvez générer une chaîne X-flippée en les associant par XOR :

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

Ainsi, si l'on génère chaque chaîne binaire de longueur N avec X bits définis, et que l'on effectue un XOR avec la chaîne initiale, on obtient toutes les chaînes X-flippées.

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

La génération de toutes les chaînes de longueur N avec X bits définis peut être effectuée, par exemple, à l'aide de la méthode suivante Gosper's Hack . Dans l'exemple de code ci-dessous, j'utilise une fonction d'inversion de l'ordre lexicographique, que j'ai initialement écrite pour cette réponse .

Double retournement

Si les bits peuvent être retournés deux fois, il est possible que la chaîne retournée X n'ait pas X bits différents de la chaîne initiale, mais seulement X-2, parce qu'un bit a été retourné puis est revenu à son état initial. Ou X-4, si le bit a été retourné 4 fois, ou si deux bits différents ont été retournés deux fois. En fait, le nombre de bits différents pourrait être X, X-2, X-4, X-6 ... jusqu'à 1 ou 0 (selon que X est pair ou impair).

Ainsi, pour générer toutes les chaînes à retournement X, vous générez toutes les chaînes avec X bits retournés, puis toutes les chaînes avec X-2 bits retournés, puis X-4, X-6 ... jusqu'à 1 ou 0.

Si X > N

Si X est supérieur à N, il est évident que certains bits seront retournés plus d'une fois. La méthode pour les générer est la même : on commence à X, on compte à rebours jusqu'à X-2, X-4, X-6... mais on ne génère des chaînes que pour des valeurs ≤ N. Donc, pratiquement, on commence à N ou N-1, selon que X-N est pair ou impair.

Nombre total de chaînes de caractères

Le nombre de chaînes de N longueurs avec X bits inversés est égal au nombre de chaînes de N longueurs avec X bits fixés, ce qui est le Coefficient binomial N choose X . Bien sûr, il faut prendre en compte les chaînes avec X-2, X-4, X-6 ... bits inversés aussi, donc le total est :

(N choisit X) + (N choisit X-2) + (N choisit X-4) + (N choisit X-6) + ... + (N choisit (1 ou 0))

Dans le cas où X est plus grand que N, vous commencez à N choose N o N choose N-1 selon que X-N est pair ou impair.

Pour votre exemple avec N=3 et X=2, le nombre total est :

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

Pour l'exemple ci-dessus avec N=10 et X=4, le nombre total est :

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

Pour l'exemple de l'autre réponse avec N=6 et X=4, le nombre correct est :

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

Exemple de code

Cet extrait de code JavaScript génère les séquences de chaînes binaires dans l'ordre lexicographique inverse (de sorte que les bits de l'ensemble se déplacent de gauche à droite), puis imprime les chaînes retournées résultantes et le nombre total pour les exemples décrits ci-dessus :

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

Answer 2

C'est en C#. Voyez si cela peut vous aider.

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