查找两个集合中 k 个元素被交换的所有组合

Question

假设我有两个列表

['a', 'b', 'c', 'd']

和

['x', 'y', 'z', 'w']

。我想创建一组另外两个列表，其中 k 个元素在两个列表之间交换：

单个元素的示例：

['x', 'b', 'c', 'd'] ['a', 'y', 'z', 'w']
['a', 'x', 'c', 'd'] ['b', 'y', 'z', 'w']
['a', 'b', 'x', 'd'] ['c', 'y', 'z', 'w']
['a', 'b', 'c', 'x'] ['d', 'y', 'z', 'w']
['y', 'b', 'c', 'd'] ['x', 'a', 'z', 'w']
['a', 'y', 'c', 'd'] ['x', 'b', 'z', 'w']
['a', 'b', 'y', 'd'] ['x', 'c', 'z', 'w']
['a', 'b', 'c', 'y'] ['x', 'd', 'z', 'w']
['z', 'b', 'c', 'd'] ['x', 'y', 'a', 'w']
['a', 'z', 'c', 'd'] ['x', 'y', 'b', 'w']
['a', 'b', 'z', 'd'] ['x', 'y', 'c', 'w']
['a', 'b', 'c', 'z'] ['x', 'y', 'd', 'w']
['w', 'b', 'c', 'd'] ['x', 'y', 'z', 'a']
['a', 'w', 'c', 'd'] ['x', 'y', 'z', 'b']
['a', 'b', 'w', 'd'] ['x', 'y', 'z', 'c']
['a', 'b', 'c', 'w'] ['x', 'y', 'z', 'd']

有没有一种有效的方法来生成这种列表？

我唯一能想到的就是在 for 循环中交换元素：

list_0 = ['a', 'b', 'c', 'd']
list_1 = ['x', 'y', 'z', 'w']

for j in range(len(list_0)):
    for i in range(len(list_1)):
        list_0[i], list_1[j] = list_1[j], list_0[i]
        print(list_0, list_1)
        list_0 = ['a', 'b', 'c', 'd']
        list_1 = ['x', 'y', 'z', 'w']

这种方法效率非常低，并且不知道如何将其扩展到交换 k 元素。

Answer 1

您可以在二进制 [0, 1] 列表上使用 itertools.product：

import itertools

list_0 = ['a', 'b', 'c', 'd']
list_1 = ['x', 'y', 'z', 'w']

lists = [list_0, list_1]

for indexes in itertools.product([0, 1], repeat=len(list_0)):
    new_list_0 = [lists[j][i] for i, j in enumerate(indexes)]
    new_list_1 = [lists[1-j][i] for i, j in enumerate(indexes)]
    print(new_list_0, new_list_1)

打印

['a', 'b', 'c', 'd'] ['x', 'y', 'z', 'w']
['a', 'b', 'c', 'w'] ['x', 'y', 'z', 'd']
['a', 'b', 'z', 'd'] ['x', 'y', 'c', 'w']
['a', 'b', 'z', 'w'] ['x', 'y', 'c', 'd']
['a', 'y', 'c', 'd'] ['x', 'b', 'z', 'w']
['a', 'y', 'c', 'w'] ['x', 'b', 'z', 'd']
['a', 'y', 'z', 'd'] ['x', 'b', 'c', 'w']
['a', 'y', 'z', 'w'] ['x', 'b', 'c', 'd']
['x', 'b', 'c', 'd'] ['a', 'y', 'z', 'w']
['x', 'b', 'c', 'w'] ['a', 'y', 'z', 'd']
['x', 'b', 'z', 'd'] ['a', 'y', 'c', 'w']
['x', 'b', 'z', 'w'] ['a', 'y', 'c', 'd']
['x', 'y', 'c', 'd'] ['a', 'b', 'z', 'w']
['x', 'y', 'c', 'w'] ['a', 'b', 'z', 'd']
['x', 'y', 'z', 'd'] ['a', 'b', 'c', 'w']
['x', 'y', 'z', 'w'] ['a', 'b', 'c', 'd']