Перестановка двух «связанных» списков в python

Question

Интересно, есть ли способ использовать itertools.permutations() (или что-то еще или подобное) в двух списках и в некотором роде связать выходные данные обоих, чтобы между их выходами было взаимно-однозначное сопоставление.

Пример: у меня есть байт x = 0xE3, x_bit = BitArray(x).bin = 11100011, который является результатом определенного порядка восьми сигналов (битовых потоков) (d0-d7), скажем [d0,d3,d4,d7,d2,d1,d6,d5]. Если я хочу изменить порядок сигналов, например, get 0xEC = 11101100 У меня есть несколько возможностей из-за неединственности двоичного домена, но две возможности будут [d0,d3,d4,d7,d6,d6,d1,d2] и [d3,d0,d4,d7,d6,d6,d1,d2]

Таким образом, вопрос заключается в том, существует ли простой способ связать выходные данные, которые приводят к 0xEC, к порядку сигналов данных (d0-d7), который приводит к требуемой битовой последовательности, например, одним способом «привязать» исходный порядок сигналов к разным битам, чтобы я получил список возможных комбинаций, но не теряя неединственности, которую обеспечивают двоичные перестановки? Сначала я думал о добавлении имени сигнала к значению бита в виде строки, но затем, конечно, это будут уникальные записи в списке, и не все действительные перестановки будут среди результата.

Это то, что я, в конце концов, буду использовать в байтовом массиве из 5-6 байтов, поэтому в конечном итоге мне придется сохранить все комбинации, которые приведут к желаемому выводу на всех позициях байтов в массиве, но в связи с время, обо всем по порядку.

import itertools
import bitstring

input_byte = 0xE3 
input_bitseq = bitstring.BitArray(inpu_byte) # 1110 0011
signal_order = ['d0','d3','d4','d7','d2','d1','d6','d5'] # input signal order

perms = list(itertools.permutations(intput_bitseq))
for x in perms:
    print(x)

Пример вывода:

('1', '1', '1', '0', '0', '0', '1', '0')
('1', '1', '0', '1', '0', '0', '1', '1')
('1', '1', '1', '0', '0', '1', '1', '0')
('1', '1', '0', '0', '1', '1', '0', '1')
('1', '1', '0', '0', '1', '1', '1', '0')
('1', '1', '0', '0', '1', '1', '0', '1')
('1', '1', '0', '0', '1', '0', '1', '1')
('1', '1', '0', '0', '1', '0', '1', '1')
('1', '1', '0', '0', '1', '1', '1', '0')

(список будет содержать 40 тыс. Записей). Теперь только подмножество этих записей на самом деле равняется 0xEC, и их, конечно, легко найти, но я хотел бы также знать, какая комбинация сигналов (d0-d7), которая отображается на различные битовые последовательности, которые все соответствуют 0xEC.

Дополнительные пояснения:

Original data:
MSB b7,b6,b5,b4,b3,b2,b1,b0 LSB
0x90        0xE3        0xF5        0xB0        0x9F        0xA2
1001 0000   1110 0011   1111 0101   1011 0000   1001 1111   1010 0010


Switch positions: b1<->b3, b0<->b2 
MSB b7,b6,b5,b4,b1,b0,b3,b2 LSB
0x90        0xEC        0xF5        0xB0        0x9F        0xA8
1001 0000   1110 1100   1111 0101   1011 0000   1001 1111   1010 1000


Switch positions: b1<->b0, b3<->b2
MSB b7,b6,b5,b4,b0,b1,b2,b3 LSB
0x90        0xEC        0xFA        0xB0        0x9F        0xA4
1001 0000   1110 1100   1111 1010   1011 0000   1001 1111   1010 0100


Switch positions: b5<->b1
MSB b7,b6,b1,b4,b0,b5,b2,b3 LSB
0x90        0xEC        0xDE        0x94        0xBB        0xA4
1001 0000   1110 1100   1101 1110   1001 0100   1011 1011   1010 0100


Switch positions: b0<->b6
MSB b7,b0,b1,b4,b6,b5,b2,b3 LSB

Final/desired output
0x90        0xEC        0xDE        0x94        0xF3        0xA4
1001 0000   1110 1100   1101 1110   1001 0100   1111 0011   1010 0100

Answer 1

Я не уверен на 100%, понимаю ли я, что вы пытаетесь сделать здесь. Насколько я понимаю, вам нужны все перестановки позиций в исходном битовом массиве, которые дают целевой битовый массив.

Наивным подходом было бы генерировать все перестановки, а затем проверять, какие из них соответствуют цели, но это были бы 8! = 40k перестановки. Это не очень много, но может быть проблемой для более длинных последовательностей или при этом довольно часто. Кроме того, вы можете получить все перестановки для единиц и нулей и распределить их в соответствии с вашим результатом; в вашем примере это будет просто 5!*3! = 720 (более сбалансированный == меньше / лучше).

Примерно так (примечание: я просто использовал строку вместо BitArray, но здесь это не имеет значения)

>>> bits = "11100011"
>>> trgt = "11101100"
>>> ones  = [i for i, e in enumerate(bits) if e == "1"]
>>> zeros = [i for i, e in enumerate(bits) if e == "0"]

>>> from itertools import permutations
>>> res = [[next(p1 if b == "1" else p2) for b in trgt] for p1, p2 in 
...        ((iter(p1), iter(p2)) for p1 in permutations(ones) 
...                              for p2 in permutations(zeros))]
...
>>> res[0]
[0, 1, 2, 3, 6, 7, 4, 5]
>>> len(res)
720
>>> set(''.join(bits[i] for i in l) for l in res)
{'11101100'}

Это дает вам решение для одного байта. Теперь, если я правильно понял эту многобайтовую часть, вы ищете одно транспонирование битов, которое можно применить к всем байтам. В этом случае число решений действительно быстро станет меньше. Вы можете использовать вышеупомянутый алгоритм, чтобы получить все решения для отдельных байтов, а затем получить set.intersection из них (сначала преобразовать списки в кортежи, чтобы сделать их хешируемыми), или получить решения для первого байта (или лучше: наиболее «сбалансированный», имеющий наименьшее количество решений для начала), а затем проверьте, какие из них также решают другие.