python - N 选择列表的 N/2 个子列表

Question

Python 中是否有一种有效的方法可以将大小为 n 的列表的所有分区分成两个大小为 n/2 的子集？我想获得一些迭代构造，以便每次迭代都提供原始列表的两个非重叠子集，每个子​​集的大小为 n/2。

例如:

A = [1,2,3,4,5,6]    # here n = 6
# some iterative construct
    # in each iteration, a pair of subsets of size n/2
    # subsets = [[1,3,4], [2,5,6]] for example for one of the iterations
    # subsets = [[1,2,5],[3,4,6]] a different iteration example

子集应该是不重叠的，例如[[1,2,3], [4,5,6]] 有效但 [[1,2,3], [3,4,5]] 不是。两个子集的顺序无关紧要，例如[[1,2,3], [4,5,6]] 不算作不同于 [[4,5,6], [1,2,3]] 因此只有这两个中的一个应该出现在迭代中。每个子集中的顺序也无关紧要，因此 [[1,2,3], [4,5,6]], [[1,3,2], [4 ,5,6]]、[[3,2,1]、[6,5,4]] 等都算作相同，因此只有其中一个应该出现在整个迭代中。

Answer 1

您将要使用 itertools.combinations去做这个。输入是您要从中选择项目的列表，第二个是要选择的项目数。

result = [list(item) for item in itertools.combinations(input, len(input) // 2)]

对于[1,2,3,4]的输入

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

作为@ShadowRanger pointed out ，如果您的列表中的顺序很重要并且您想要所有排列，您需要将 itertools.permutations 替换到解决方案中。

result = [list(item) for item in itertools.permutations(input, len(input) // 2)]
# [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]

编辑

仔细阅读您的问题后，不清楚您是想要所有 n/2 排列，还是想要一个 lits 列表，其中每个元素都是另一个排列的两个“一半”的列表。

为此，您可以执行以下操作(结合一些索引帮助 from @Blckknght )

result = [[list(item[::2]), list(item[1::2])] for item in itertools.permutations(input)]

在这种情况下，[1,2,3,4] 的输出将是

[[[1, 3], [2, 4]], [[1, 4], [2, 3]], [[1, 2], [3, 4]], [[1, 4], [3, 2]], [[1, 2], [4, 3]], [[1, 3], [4, 2]], [[2, 3], [1, 4]], [[2, 4], [1, 3]], [[2, 1], [3, 4]], [[2, 4], [3, 1]], [[2, 1], [4, 3]], [[2, 3], [4, 1]], [[3, 2], [1, 4]], [[3, 4], [1, 2]], [[3, 1], [2, 4]], [[3, 4], [2, 1]], [[3, 1], [4, 2]], [[3, 2], [4, 1]], [[4, 2], [1, 3]], [[4, 3], [1, 2]], [[4, 1], [2, 3]], [[4, 3], [2, 1]], [[4, 1], [3, 2]], [[4, 2], [3, 1]]]

编辑2

由于顺序无关紧要，但您需要一种类似于上一种方法(列表的列表的列表)的方法，由于数组切片，最后一种方法有点棘手。一种替代方法是使用 set 和 frozenset构造初始信息(而不是列表)，因为在 set 中，检查是否相等时顺序无关紧要。这将自动允许我们删除重复项。然后，如果您愿意，我们可以添加一个额外的步骤来转换回列表。

from itertools import permutations
tmp = set([frozenset([frozenset(k[::2]),frozenset(k[1::2])]) for k in permutations(input)]) 
result = [[list(el) for el in item] for item in tmp];

这会产生

[[[1, 2], [3, 4]], [[2, 3], [1, 4]], [[1, 3], [2, 4]]]