将列表划分为两个非空列表的所有方法 [英] All ways of partitioning a list into two non-empty lists

问题描述

[0.0、1.0、2.0、3.0、4.0]

[0.0, 1.0, 2.0, 3.0, 4.0]

我有5个数字和两组，分别是左和右.每个数字都有两个选择-可以向左或向右移动.我需要一个包含列表[0,1,2,3,4]的所有分区为两个非空部分的列表.例如:[[[[0]，[1,2,3,4])，([0,1，[2,3,4])，...，]

I have 5 numbers and two groups, left and right. Each number has two choices - it can go left or right. I need a list that contains all partitioning of the list [0,1,2,3,4] into two non empty parts. For example: [([0], [1,2,3,4]), ([0,1], [2,3,4]), ...,]

请注意，总共有(2 ^ 5 -2)/2个分区-顺序无关紧要，我也不想重复.意思是我不想要这样的东西(如果我的列表是 [1,2,3,4]):

Note that there are a total of (2^5 -2)/2 partitioning - order doesn't matter and I don't want repeats. Meaning I don't want something like this (if my list was [1,2,3,4]):

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

我研究了所有itertools函数，但似乎没有一个起作用.

I've looked into all of the itertools functions and none seem to work.

列表[i for range(16)中的i]，它具有16个元素，如果执行以下操作，这就是我看到的内容:

for list [i for i in range(16)], which has 16 elements, If I do the following, this is what I see:

 n = len(l)//2 + 1
>>> xs = list(chain(*[combinations(l, i) for i in range(1, n)]))
>>> pairs = [(list(x), list(set(l) - set(x))) for x in xs]
>>> print len(pairs)
    39202
>>> (2**16-2)/2
    32767

实际上，它对于包含6个元素的列表也不起作用.我不明白为什么...

In fact, it doesn't work for a list with 6 elements either. I don't see why...

所有偶数长度列表都会出现此问题.例如，当我尝试一个长度为2的列表时，我得到:

The problem occurs for all even length lists. For example, when I try a length 2 list, I get:

[([0.0]，[1.0])，([1.0]，[0.0])]

[([0.0], [1.0]), ([1.0], [0.0])]

推荐答案

itertools 中有这些东西，也许您只是找对了地方.

The stuff is there in itertools, maybe you just weren't looking in the right places.

这是Codez:

from collections import OrderedDict
from itertools import chain, combinations

def partition(L):
    n = len(L)//2 + 1
    xs = chain(*[combinations(L, i) for i in range(1, n)])
    pairs = (tuple(sorted([x, tuple(set(L) - set(x))])) for x in xs)
    return OrderedDict.fromkeys(pairs).keys()

输出:

>>> for pair in partition([1,2,3,4]):
...     left, right = map(list, sorted(pair, key=len))
...     print left, right
...
[1] [2, 3, 4]
[2] [1, 3, 4]
[3] [1, 2, 4]
[4] [1, 2, 3]
[1, 2] [3, 4]
[1, 3] [2, 4]
[1, 4] [2, 3]

这篇关于将列表划分为两个非空列表的所有方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！