N选择一个列表的N/2个子列表 [英] N choose N/2 sublists of a list

问题描述

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

Is there an efficient way in Python to get all partitions of a list of size n into two subsets of size n/2? I want to get some iterative construct such that each iteration provides two non-overlapping subsets of the original list, each subset having size 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]]等都相同，因此在整个迭代中只有一个出现.

The subsets should be non-overlapping, e.g. [[1,2,3], [4,5,6]] is valid but [[1,2,3], [3,4,5]] is not. The order of the two subsets does not matter, e.g. [[1,2,3], [4,5,6]] does not count as different from [[4,5,6], [1,2,3]] and thus only one of those two should appear in an iteration. The order within each subset also does not matter, so [[1,2,3], [4,5,6]], [[1,3,2], [4,5,6]], [[3,2,1], [6,5,4]], etc. all count as the same and so only one of them should show up in whole iteration.

推荐答案

这是一个基于itertools的生成器，我认为它可以精确生成所需的值.

Here's an itertools-based generator that I think yields exactly the values you want.

def sub_lists(sequence):
    all_but_first = set(sequence[1:])
    for item in itertools.combinations(sequence[1:], len(sequence)//2 - 1):
        yield [[sequence[0]] + list(item), list(all_but_first.difference(item))]

与Suever回答中基于permutations的方法相比，我以两种方式避免了近乎重复的输出.首先，我通过强制所有结果在第一个子列表中具有输入序列的第一个值来避免同时产生[["a", "b"], ["c", "d"]]和[["c", "d"], ["a", "b"]].我避免通过使用集减法构建第二个子列表来产生[["a", "b"], ["c", "d"]]和[["a", "b"], ["d", "c"]].

I avoid near-duplicate outputs in two ways as compared to a permutations based approach in Suever's answer. First, I avoid yielding both [["a", "b"], ["c", "d"]] and [["c", "d"], ["a", "b"]] by forcing all the results to have the first value of the input sequence in the first sublist. I avoid yielding [["a", "b"], ["c", "d"]] and [["a", "b"], ["d", "c"]] by building the second sublist using set-subtraction.

请注意，产生嵌套元组可能比嵌套列表更自然.为此，只需将最后一行更改为:

Note that yielding nested tuples might be a little more natural than nested lists. To do that, just change the last line to:

yield (sequence[0],) + item, tuple(all_but_first.difference(item))

这篇关于N选择一个列表的N/2个子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！