时间戳

首页 > 解决方案 > 在python中将列表分成两半而不重复的每种方法

python - 在python中将列表分成两半而不重复的每种方法

问题描述

我有一个独特项目的列表，例如这个：

myList = ['a','b','c','d','e','f','g','h','i','j']

我想找到所有可能的方法将这个列表分成两半。例如，这是一种方式：

A = ['g','b','j','d','e']
B = ['f','a','h','i','c']

我想到的第一件事是从列表中找到 5 个项目的所有组合，并将其设为 sub-list A，然后其他所有内容将是 sub-list B：

for combination in itertools.combinations(myList, 5):
    A = combination
    B = everything_else()

然而，这不起作用，因为我会得到每个结果两次。例如，如果其中一种组合是['a','b','c','d','e']then，从这个循环中，我将得到：

A = ['a','b','c','d','e']
B = ['f','g','h','i','j']

但后来，当组合['f','g','h','i','j']出现时，我也会得到：

A = ['f','g','h','i','j']
B = ['a','b','c','d','e']

出于我的目的，两组组合是相同的，因此我应该只得到一次这个结果。我怎样才能做到这一点？

编辑：为了澄清，我想要每一种可能的方式来拆分列表（当然，没有任何元素同时出现在两者A中B）。

标签： python

解决方案

自由应用集合可以很容易地解决这个问题：

def split(items):
    items = frozenset(items)
    combinations = (frozenset(combination) for combination in itertools.combinations(items, len(items) // 2))
    return {frozenset((combination, items - combination)) for combination in combinations}

哪个按预期工作：

>>> split([1, 2, 3, 4])
{
    frozenset({frozenset({2, 4}), frozenset({1, 3})}), 
    frozenset({frozenset({1, 4}), frozenset({2, 3})}), 
    frozenset({frozenset({3, 4}), frozenset({1, 2})})
}

这遵循了您的基本想法——我们使用原始大集合中的五个元素的组合，然后获取其他元素（这很容易，只需设置差异）。然后，我们也可以通过设置对来简化重复项，因此顺序无关紧要，任何顺序的两个都被视为等效。然后我们将外部结构设置为一个集合，这意味着重复项被删除。

在这里使用frozensetoverset是因为可变集合不能是其他集合的成员。不过，我们在这里不需要任何突变，所以这不是问题。

显然这不是最有效的解决方案，因为我们仍在生成重复项，但这可能是实现它的最简单和最简单的方法。

这也很明显地导致了一个简单的升级，以便稍后扩展您在评论中给出的问题：

def split(items, first_length=None):
    items = frozenset(items)
    if first_length == None:
        first_length = len(items) // 2
    combinations = (frozenset(combination) for combination in itertools.combinations(items, first_length))
    return {frozenset((combination, items - combination)) for combination in combinations}

推荐阅读