Как рассчитать, сколько битовых последовательностей размера n с установленным k битами и c изменениями битовых значений существует?

Question

Мы знаем, что вычисление количества битовых последовательностей n-длины с установленным k битами равно C (n, k) = n! / (K! (nk)!) *.

Но я недавно спросил себя, как вы можете подумать об этой проблеме, если задано другое условие: количество битовых значений изменяется.Например, для n = 4 и k = 2 у нас есть 6 решений:

1-0011

2-0101

3-0110

4-1001

5-1010

6-1100

Теперь предположим, что мы хотим получить последовательности только с двумя изменениямив битовых значениях.Теперь есть только два решения:

1-0110 (начинается с 0, изменяется на 1, затем изменяется на 0 после).2-1001 (начинается с 1, изменяется на 0, затем изменяется на 1 после).

Как быстро рассчитать количество решений (без генерации каждой комбинации и подсчета)?Я думаю, что можно считать начальный бит изменением, не слишком меняя ответ, поэтому не стесняйтесь делать это.

Дополнительный вопрос: учитывая комбинацию с установленными битами k и c количество битовых изменений, какой самый быстрый способ генерировать следующую комбинацию с тем же количеством k битов и c количеством битовых изменений?

Answer 1

Предположим, у нас есть ряд n неотличимых объектов, скажем, красных шаров.Сколько способов мы можем разделить их на k непустые группы?Это довольно легко, правда?Первая группа начинается с первого объекта, а каждая другая группа должна начинаться с какого-то другого объекта.Таким образом, мы можем построить раздел, выбрав первый объект и k-1 из n-1 оставшихся объектов, что мы можем сделать C(n-1, k-1) различными способами.

Теперь предположим, что у нас есть еще одна строка mнеразличимые объекты, скажем, синие шары, и мы хотим разделить их на j групп.Но это точно та же проблема, и решение должно быть C(m-1, j-1).

ОК, теперь предположим, что мы хотим построить ряд объектов, из которых n красного и m синего, вкоторых в общей сложности c групп, чередующихся между красным и синим.Теперь есть две возможности:

1. Строка начнется с красного шара.Если c чётно, то будут c/2 красные группы с чередованием c/2 синих групп.Если c нечетно, будет больше одной красной группы, чем синей группы, поэтому будет ceil(c/2) красных групп и floor(c/2) синих групп.(Если c четное, то и floor(c/2), и ceil(c/2) равны c/2. Таким образом, мы можем использовать формулы floor и ceil в обоих случаях.)

   В любом случае мы можем разделитькрасные шары в группы и синие шары в группы независимо, а затем чередовать их.Таким образом, существует C(n - 1, ceil(c/2) - 1) × C(m - 1, floor(c/2) - 1) возможных договоренностей.

2. Строка начнется с синего шара.Точно такой же анализ применяется, за исключением того, что n и m поменялись местами.

Таким образом, общее количество договоренностей:

C(n - 1, ceil(c/2) - 1) × C(m - 1, floor(c/2) - 1) +
C(n - 1, floor(c/2) - 1) × C(m - 1, ceil(c/2) - 1)

Это простопереписывание вашей задачи, в которой было k единиц и n-k нулей, с c-1 переходами (что приводит к c группам).Я оставлю оставшийся шаг алгебры читателю (а также упрощение для нечетного числа групп).

Answer 2

Это проблема с шариками и урнами .Вы начинаете с последовательности чередующихся 0 s и 1 s с необходимым количеством битовых изменений, а затем помещаете оставшиеся 0 s и 1 s в урны.

Пример: n=20, k=8, c=4.

Рассмотрим случай, когда бистринг начинается с 0.Начните с (c+1) чередующихся битов, чтобы получить c изменения:

01010

На этом этапе вам все еще нужно разместить 9 0 с и 6 1 с.Давайте сначала разместим 0.Сколько способов мы можем разместить 9 оставшихся 0 с, не добавляя битовых изменений?Есть 3 «урны» для размещения «шаров» (0 с):

0 ... 1 0 ... 1 0 ...
   ^       ^       ^

Существует (9+3-1) choose 3 способов размещения 9 шаров в 3 урны.

Как только0 s размещены, нам также нужно разместить 1 s.По аналогичным соображениям, у нас есть 6 шаров (1 s) для размещения в 2 урнах, что можно сделать (6+2-1) choose 2 способами.

Так как расположение 0 s и 1 sнезависимо, мы умножаем результаты: есть ((9+3-1) choose 3) * ((6+2-1) choose 2) способов для битовой строки длиной 20 с 8 1 с, чтобы иметь 4-битные изменения, , если вы начинаете с 0.

Вам все еще нужно добавить оставшийся регистр (начиная с 1, поэтому первый шаг приводит к 10101), который может быть решен точно так же.