将列表划分为两个非空列表的所有方法
All ways of partitioning a list into two non-empty lists
[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]), ...,]
请注意,总共有 (2^5 -2)/2 个分区 - 顺序无关紧要,我不想重复。意思是我不想要这样的东西(如果我的列表是[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 函数,none 似乎有效。
编辑:
对于列表 [i for i in range(16)],它有 16 个元素,如果我执行以下操作,这就是我看到的:
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 个元素的列表。我不明白为什么...
所有偶数长度列表都会出现此问题。例如,当我尝试长度为 2 的列表时,我得到:
[([0.0], [1.0]), ([1.0], [0.0])]
这些东西在 itertools
中,也许您只是没找对地方。
这是代码:
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]
[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]), ...,]
请注意,总共有 (2^5 -2)/2 个分区 - 顺序无关紧要,我不想重复。意思是我不想要这样的东西(如果我的列表是[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 函数,none 似乎有效。
编辑: 对于列表 [i for i in range(16)],它有 16 个元素,如果我执行以下操作,这就是我看到的:
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 个元素的列表。我不明白为什么...
所有偶数长度列表都会出现此问题。例如,当我尝试长度为 2 的列表时,我得到:
[([0.0], [1.0]), ([1.0], [0.0])]
这些东西在 itertools
中,也许您只是没找对地方。
这是代码:
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]