Чисто практическая задачка. Информация о состоянии некого объекта передаётся при помощи двоичного кода (например, включением-выключением некоторого сигнала по границам некоторых периодов равной продолжительности, которую можно считать единичной). Код является периодическим и циклическим, т.е. постоянно повторяется, и начало/конец кодовой комбинации никак не обозначены, т.е. всё, что получается друг из друга циклической перестановкой, считается одним и тем же кодом. При этом длина кодового цикла заранее задана, и кроме того, задано, что цикл обязан состоять из двух половин, являющихся побитной инверсией друг друга.
Вопрос: как посчитать число различимых кодовых комбинаций для любой заданной длины половины цикла (натурального числа)?
Как это теоритечески объясняется, я не уверен, но вообще вот эта последовательность: https://oeis.org/A000016/list
|
n | | a(n) |
0 | | 1 |
1 | | 1 |
2 | | 1 |
3 | | 2 |
4 | | 2 |
5 | | 4 |
6 | | 6 |
7 | | 10 |
8 | | 16 |
9 | | 30 |
10 | | 52 |
11 | | 94 |
12 | | 172 |
13 | | 316 |
14 | | 586 |
15 | | 1096 |
16 | | 2048 |
17 | | 3856 |
18 | | 7286 |
19 | | 13798 |
20 | | 26216 |
21 | | 49940 |
22 | | 95326 |
23 | | 182362 |
24 | | 349536 |
25 | | 671092 |
26 | | 1290556 |
27 | | 2485534 |
28 | | 4793492 |
29 | | 9256396 |
30 | | 17895736 |
31 | | 34636834 |
32 | | 67108864 |
33 | | 130150588 |
34 | | 252645136 |
35 | | 490853416 |
Хорошее приближение дает формула a(n) = 2^n/(2*n).
Что касается самой формулировки задачки - то "двойной" код длиной 2n, состоящий из "ритмически одинаковых", просто побитово инвертированных половинок длины n, можно представить проще - как двоичный код длины n, где каждый разряд соответствует месту, где состояние сигнала меняется или не меняется (соотв. 1 или 0), тогда условие, что половины именно инвертированы, преобразуется в то, что в дифференциальном коде должно быть всегда нечётное число единиц.
Дальше нам надо по-прежнему собрать все возможные такие коды в кучки таких, которые переходят друг в друга при циклическом сдвиге, и пересчитать эти кучки - в чём и состоит суть задачи.
Я банально перебрал варианты.
for halflength in range(1, 21):
binaryformat = '{:0'+str(halflength)+'b}'
combinations = set()
for i in range(2**halflength):
code = binaryformat.format(i)
code = code+''.join(['1' if c=='0' else '0' for c in code])
normalizedcode = min([code[j:]+code[:j] for j in range(len(code))])
combinations |= {normalizedcode}
combinations = sorted(list(combinations))
print(f'Length {halflength}, combinations {len(combinations)}')
#print(combinations)
ЦитироватьLength 1, combinations 1
Length 2, combinations 1
Length 3, combinations 2
Length 4, combinations 2
Length 5, combinations 4
Length 6, combinations 6
Length 7, combinations 10
Length 8, combinations 16
Length 9, combinations 30
Length 10, combinations 52
Length 11, combinations 94
Length 12, combinations 172
Length 13, combinations 316
Length 14, combinations 586
Length 15, combinations 1096
Length 16, combinations 2048
Length 17, combinations 3856
Length 18, combinations 7286
Length 19, combinations 13798
Length 20, combinations 26216