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

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)}.

Answer 2

您可以分三步完成。首先，从列表 B 创建一个字典，其中的项作为键，索引作为值。在你的例子中，你的列表 B 的字典：

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

  7 - [0]
'x' - [1, 2]

然后，遍历您的列表 A 并构建一个索引，将列表 A 索引映射到其相应的列表 B 索引。即：

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

0 - [1, 2]
1 - [1, 2]
2 - [0]

由此，您可以生成所有有效的映射。编写代码应该很容易，根据上面的索引，将生成 [1, 2, 0] 和 [2, 1, 0].

Answer 3

这是一种方法。我的 perms 函数生成所有有效排列。首先，我为 B 中的每个元素收集索引，然后我通过始终为 A 中的每个项目选择一个仍然可用的索引来递归构建和生成排列，直到准备好生成排列。

from collections import defaultdict

def perms(A, B):
    indexes = defaultdict(set)
    for i, e in enumerate(B):
        indexes[e].add(i)
    def find(perm):
        k = len(perm)
        if k == len(A):
            yield perm
            return
        I = indexes[A[k]]
        for i in list(I):
            I.remove(i)
            yield from find(perm + (i,))
            I.add(i)
    yield from find(())

用法：

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

for perm in perms(A, B):
    print(perm)

输出：

(1, 2, 0)
(2, 1, 0)

Answer 4

这是 Python 中的内容。我使用字符串进行哈希处理，因为我不熟悉如何在 Python 中将集合和数组作为递归参数传递，尽管它们可能更有效。

A = ['x', 'x', 7, 'y', 8, 8]
B = [7, 'x', 8, 'x', 8, 'y']
H = {}

# record the indexes of elements in B
for i in xrange(0,len(B)):
  if B[i] in H:
    H[ B[i] ].append(str(i)) 
  else:
    H[ B[i] ] = [str(i)]

# build permutations in the order that the elements are encountered in A
def perms(perm,i,visited,l):
  if i==l:
    print perm
    return
  for j in H[ A[i] ]:
    if j not in visited:
      perms(perm + j,i + 1,visited + j,l)

perms("",0,"",len(A))

输出：

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

How to get all orderings of a list such that the list is equal to another list?

python

sorting

algorithm

list

permutation