python - 如何获得一个列表的所有顺序，使该列表等于另一个列表？

Question

我有列表 A 和 B，它们可以有重复项，例如:

A = ['x', 'x', 7]
B = [7, 'x', 'x']

现在我想要将列表 B 排列到列表 A 中的所有索引排列:

[1, 2, 0]    # because [B[1], B[2], B[0]] == A
[2, 1, 0]    # because [B[2], B[1], B[0]] == A

有没有办法在不遍历所有可能排列的情况下实现这一点？我已经在用了

import itertools
for p in itertools.permutations(range(len(B))):
    if A == permute(B,p):

遍历所有可能的排列并检查我想要的排列，但我想更快地找到正确的排列。

Answer 1

你应该把你的问题分解成两部分:

• 首先找到将 B 映射到 A 的特定排列 sigma_0
• 找到将 B 映射到自身的所有排列的集合S_B

那么你正在寻找的集合就是{sigma_0\circ\sigma, sigma\in S_B}。

现在问题变成了:我们如何确定S_B？为此，您可以观察到如果将集合 {0,1,2,..,n}(在您的情况下为 n=2)编写为A_1\cup .. A_k，其中每个 A_i 对应于 B 中对应于第 i 个元素的索引(在您的例子中，你会有 A_1 = {1,2} 和 A_2 = {0})，那么 S_B 的每个元素都可以写成唯一的方式作为乘积 tau_1\circ .. tau_k，其中每个 tau_i 都是作用于 A_i 的排列。

因此，在您的情况下 S_B = {id, (1,2)} 并且您可以采用 sigma_0 = (0,2)。因此，您所追求的集合是 {(0,2), (2,0,1)}。