Python：如何有效地创建数组所有可能的 2 元素交换？

Question

我尝试生成给定数组的所有可能的 2 元素交换。

例如：

candidate = [ 5, 9, 1, 8, 3, 7, 10, 6, 4, 2]

result = [[ 9,  5,  1,  8,  3,  7, 10,  6,  4,  2]
[ 1,  9,  5,  8,  3,  7, 10,  6,  4,  2]
[ 8,  9,  1,  5,  3,  7, 10,  6,  4,  2]
[ 3,  9,  1,  8,  5,  7, 10,  6,  4,  2]
[ 7,  9,  1,  8,  3,  5, 10,  6,  4,  2]
[10,  9,  1,  8,  3,  7,  5,  6,  4,  2]
[ 6,  9,  1,  8,  3,  7, 10,  5,  4,  2]
[ 4,  9,  1,  8,  3,  7, 10,  6,  5,  2]
[ 2,  9,  1,  8,  3,  7, 10,  6,  4,  5]
[ 5,  1,  9,  8,  3,  7, 10,  6,  4,  2]
[ 5,  8,  1,  9,  3,  7, 10,  6,  4,  2]
[ 5,  3,  1,  8,  9,  7, 10,  6,  4,  2]
[ 5,  7,  1,  8,  3,  9, 10,  6,  4,  2]
[ 5, 10,  1,  8,  3,  7,  9,  6,  4,  2]
[ 5,  6,  1,  8,  3,  7, 10,  9,  4,  2]
[ 5,  4,  1,  8,  3,  7, 10,  6,  9,  2]
[ 5,  2,  1,  8,  3,  7, 10,  6,  4,  9]
[ 5,  9,  8,  1,  3,  7, 10,  6,  4,  2]
[ 5,  9,  3,  8,  1,  7, 10,  6,  4,  2]
[ 5,  9,  7,  8,  3,  1, 10,  6,  4,  2]
[ 5,  9, 10,  8,  3,  7,  1,  6,  4,  2]
[ 5,  9,  6,  8,  3,  7, 10,  1,  4,  2]
[ 5,  9,  4,  8,  3,  7, 10,  6,  1,  2]
[ 5,  9,  2,  8,  3,  7, 10,  6,  4,  1]
[ 5,  9,  1,  3,  8,  7, 10,  6,  4,  2]
[ 5,  9,  1,  7,  3,  8, 10,  6,  4,  2]
[ 5,  9,  1, 10,  3,  7,  8,  6,  4,  2]
[ 5,  9,  1,  6,  3,  7, 10,  8,  4,  2]
[ 5,  9,  1,  4,  3,  7, 10,  6,  8,  2]
[ 5,  9,  1,  2,  3,  7, 10,  6,  4,  8]
[ 5,  9,  1,  8,  7,  3, 10,  6,  4,  2]
[ 5,  9,  1,  8, 10,  7,  3,  6,  4,  2]
[ 5,  9,  1,  8,  6,  7, 10,  3,  4,  2]
[ 5,  9,  1,  8,  4,  7, 10,  6,  3,  2]
[ 5,  9,  1,  8,  2,  7, 10,  6,  4,  3]
[ 5,  9,  1,  8,  3, 10,  7,  6,  4,  2]
[ 5,  9,  1,  8,  3,  6, 10,  7,  4,  2]
[ 5,  9,  1,  8,  3,  4, 10,  6,  7,  2]
[ 5,  9,  1,  8,  3,  2, 10,  6,  4,  7]
[ 5,  9,  1,  8,  3,  7,  6, 10,  4,  2]
[ 5,  9,  1,  8,  3,  7,  4,  6, 10,  2]
[ 5,  9,  1,  8,  3,  7,  2,  6,  4, 10]
[ 5,  9,  1,  8,  3,  7, 10,  4,  6,  2]
[ 5,  9,  1,  8,  3,  7, 10,  2,  4,  6]
[ 5,  9,  1,  8,  3,  7, 10,  6,  2,  4]]

我目前通过使用两个嵌套的 for 循环来实现这一点：

    neighborhood = []
    for node1 in range(candidate.size - 1):
        for node2 in range(node1 + 1, candidate.size):
            neighbor = np.copy(candidate)
            neighbor[node1] = candidate[node2]
            neighbor[node2] = candidate[node1]
            neighborhood.append(neighbor)

数组越大，效率就越低，速度就越慢。这里是否有更有效的方法也可以处理具有三位数内容的数组？

谢谢你！

Answer 1

如果你需要一一使用这些数组，你可以使用生成器（这样你就不需要全部记住它们，你只需要很少的空间）：

from itertools import combinations

def gen(lst):
    for i, j in combinations(range(len(lst)), 2):
        yield lst[:i] + lst[j] + lst[i:j] + lst[i] + lst[j:]

然后你可以这样使用它：

for lst in gen(candidate):
    # do something with your list with two swapped elements

这将节省大量空间，但总体来说可能仍然很慢。

这是使用 NumPy 的解决方案。这并不节省空间（因为它会记住所有可能的带有交换元素的列表），但由于 NumPy 优化，它可能会快得多。试一试！

from itertools import combinations
from math import comb

arr = np.tile(candidate, (comb(len(candidate), 2), 1))
indices = np.array(list(combinations(range(len(candidate)), 2)))
arr[np.arange(arr.shape[0])[:, None], indices] = arr[np.arange(arr.shape[0])[:, None], np.flip(indices, axis=-1)]

示例（带有candidate = [0, 1, 2, 3]）：

>>> arr
array([[1, 0, 2, 3],
       [2, 1, 0, 3],
       [3, 1, 2, 0],
       [0, 2, 1, 3],
       [0, 3, 2, 1],
       [0, 1, 3, 2]])

请注意，math.comb（它为您提供具有 2 个交换元素的可能列表的总数）仅适用于 python >= 3.8。请查看这个问题，math.comb了解如果您使用的是较旧的 python 版本，如何替换。