k 플립이있는 다른 바이너리 문자열의 수

Question

길이가 N 인 이진 문자열 (< 10^5)이 주어진 곳에 문제가 발생했습니다. 정확히 X (< 10^5)가 뒤집어 질 수 있습니다. 얼마나 많은 다른 문자열이 가능합니까? 나는 이것에 관해서 생각을하지 못한다.하지만 그것은 dp를 사용하여 해결할 수는 있지만, 재귀와 함께 할 수는 없다. Plz 도움말?

예 : 2 플립 1 1 1 이다 도포 한 후에 형성 될 수있는 이진 N 문자열 = 3 1 1 1 및 X = 2 개 새로운 이진 스트링을 고려 (1 차/2 차/제 3 비트를 플립 회) 0 0 1 (뒤집힌 제 1 및 제 2 비트) 1 0 0 (대칭 2 및 3 비트) 0 1 0 (대칭 1 · 3 비트)

Answer 1

이것은 C#에서이다. 도움이되는지 확인하십시오.

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

Answer 2

찾기 X-뒤집어 문자열는

예를 들면 고려 N = 10 인 경우, X = 4, 초기 문자열 :

flipped: 0000111111 

4 때문에 비트가 다르다 :

initial: 0011010111 

후 이것이 X-대칭 문자열의 예가 될 것이다. 당신이 두 개의 문자열을 XOR하면 얻을 다음 XOR-ED 문자열에서 4 세트 비트 (들)이 반전 된 4 비트의 위치를 ​​나타냅니다

initial: 0011010111 
flipped: 0000111111 
XOR-ed: 0011101000 

.

이제 이것을 거꾸로 생각해보십시오. 당신이 초기 문자열, 4 세트 비트 문자열을 가지고 있다면, 당신은에 의해 X-뒤집어 문자열을 생성 할 수 있습니다를 XOR을 - 보내고 :

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

을 그래서 당신은 X 세트 길이 N의 모든 바이너리 문자열을 생성하는 경우 비트, 그리고 당신은 원래 문자열로 XOR, 당신은 모든 X 플립 문자열을 얻을.

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

예를 들어, X 세트 비트를 사용하여 모든 N 길이 문자열을 생성 할 수 있습니다. Gosper's Hack. 아래의 코드 예제에서는 역순 사전 순서 함수를 사용합니다.이 함수는 원래 this answer으로 작성했습니다.

두 번 틀지

비트가 두 번 뒤집어 될 수 있다면, 하나의 비트 때문에, X가없는 X-뒤집어 문자열이 초기 문자열에서 다른,하지만 X-2 비트 가능성이 있습니다 뒤집어 원래 상태로 되돌 렸습니다. 또는 X-4, 비트가 4 번 뒤집 혔거나 두 개의 다른 비트가 두 번 뒤집 으면. 사실, 다른 비트의 수는 X, X-2, X-4, X-6 ... 1 또는 0 (X가 홀수인지 짝수인지에 따라 다름) 일 수 있습니다.

따라서 X 플립 된 모든 문자열을 생성하려면 X 플립 된 비트가있는 모든 문자열을 생성 한 다음 X-2 플립 된 비트가있는 모든 문자열을 생성 한 다음 X-4, X-6 ...을 1 또는 0으로 만듭니다.X는 N보다 큰 경우에는 X> N은

다음 명백히 몇몇 비트들은 한 번 이상 대칭 될 경우

. X에서 시작하여 X-2, X-4, X-6까지 카운트 다운하지만 ≤ N 값의 문자열 만 생성합니다. 따라서 실제적으로 N 또는 N- XN이 짝수 또는 홀수인지 여부에 따라 1입니다. 문자열

X와 N 길이 문자열의 개수

전체 수의 비트를 반전시켜 Binomial CoefficientN choose X 인 X 세트 비트를 가진 N 길이 스트링의 개수와 동일. 물론 X-2, X-4, X-6 ... 문자열을 고려해야합니다. 따라서 합계는 다음과 같습니다.

(N을 선택 X) + (N은 X를 선택하십시오. (X 또는 N을 선택하십시오)

X가 N보다 큰 경우 XN이 짝수 또는 홀수인지 여부에 따라 N choose N 또는 N choose N-1에서 시작하십시오. N = 3 X = 2와 함께 예를 들어

총 개수이다

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

: N = 10, X = 4, 총 수는 위에서 예를 들면

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

N = 6 다른 답변의 예

하고 정확한 개수 = 4 인 X :

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

예제 코드

이 JavaScript 코드 조각은 역 사전 식 순서로 (설정 비트가 왼쪽에서 오른쪽으로 이동하도록) 이진 문자열의 시퀀스를 생성 한 다음 위에서 설명한 예제의 결과 반전 문자열과 총 개수를 인쇄합니다 : X에 의해

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