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。请看this question了解如何替换 math.comb，以防您使用的是较旧的 python 版本。