python - python中两个 "linked"列表的排列

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) 的数据信号顺序所需的位序列，例如以一种方式将原始信号顺序“ Hook ”到不同的位，以便我最终得到可能组合的列表，但不会失去二进制排列提供的非唯一性？我首先考虑将信号名称作为字符串附加到位值，但是当然它将是列表中的唯一条目，并且并非所有有效排列都会出现在结果中。

这是我最终将在 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')

(列表将有 40k 左右的条目)。现在，只有这些条目的一个子集实际上等于 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排列。这并不是很多，但对于较长的序列或经常这样做时可能会出现问题。或者，您可以获取 1 和 0 的所有排列并分配它们以适合您的结果；这些只是 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其中(首先将列表转换为元组以使它们可散列)，或者获取第一个字节的解决方案(或更好:最“平衡”的一个，开始时具有最少数量的解决方案)，然后检查其中哪一个还解决了其他问题。