在Python中设置分区
我有一个[1,2,3]
我想使用数组的所有元素进行所有可能的组合：
结果：
[[1], [2], [3]] [[1,2], [3]] [[1], [2,3]] [[1,3], [2]] [[1,2,3]]
既然这个不错的问题已经复活，这里有一个新的答案。
这个问题是recursion地解决的：如果你已经有一个n-1元素的分区，你如何使用它来分割n个元素？ 将第n个元素放置在其中一个现有的子集中，或将其添加为新的单个子集。 这一切都需要; 没有itertools ，没有设置，没有重复的输出，总共只有n个调用partition() ：
def partition(collection): if len(collection) == 1: yield [ collection ] return first = collection[0] for smaller in partition(collection[1:]): # insert `first` in each of the subpartition's subsets for n, subset in enumerate(smaller): yield smaller[:n] + [[ first ] + subset] + smaller[n+1:] # put `first` in its own subset yield [ [ first ] ] + smaller something = list(range(1,5)) for n, p in enumerate(partition(something), 1): print(n, sorted(p))
输出：
1 [[1, 2, 3, 4]] 2 [[1], [2, 3, 4]] 3 [[1, 2], [3, 4]] 4 [[1, 3, 4], [2]] 5 [[1], [2], [3, 4]] 6 [[1, 2, 3], [4]] 7 [[1, 4], [2, 3]] 8 [[1], [2, 3], [4]] 9 [[1, 3], [2, 4]] 10 [[1, 2, 4], [3]] 11 [[1], [2, 4], [3]] 12 [[1, 2], [3], [4]] 13 [[1, 3], [2], [4]] 14 [[1, 4], [2], [3]] 15 [[1], [2], [3], [4]]
不像我的意见build议，我无法快速find基于itertools相对较快的解决scheme！ 编辑：这不再是相当真实的，我有一个相当短的（但缓慢和不可读）使用itertools大部分解决scheme，看到答案的结束。 这就是我所得到的：
我们的想法是，我们find加起来到列表长度的所有整数组合，然后得到具有该长度片段的列表。
例如，对于长度为3的列表，组合或分区是（3），（2,1），（1,2）和（1,1,1）。 所以我们返回列表的前三项; 第一个2，然后是第二个1; 第一个1然后是下2和第一个1，然后是下一个1，然后是下一个1。
我从这里得到整数分配的代码。 然而，分区函数并不返回分区的所有排列（即，对于3，它只会返回（3），（2,1）和（ itertools.permutations ））。所以我们需要在每个itertools.permutations上调用itertools.permutations然后我们需要删除重复项 – 就像permutations([1, 2, 3])是[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] permutations([1, 1, 1]) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] ; permutations([1, 1, 1])是[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] 。删除重复的简单方法是将每个元组列表转换为一个set 。
然后，剩下的就是得到元组长度的列表。 例如， f([1, 2, 3], [0, 0, 1, 2, 1, 0])变为[[0], [0, 1], [2, 1, 0]] 。
我对此的定义是这样的：
def slice_by_lengths(lengths, the_list): for length in lengths: new = [] for i in range(length): new.append(the_list.pop(0)) yield new
现在我们把所有的东西结合
def subgrups(my_list): partitions = partition(len(my_list)) permed = [] for each_partition in partitions: permed.append(set(itertools.permutations(each_partition, len(each_partition)))) for each_tuple in itertools.chain(*permed): yield list(slice_by_lengths(each_tuple, deepcopy(my_list))) >>> for i in subgrups(my_list): print(i) [[1], [2], [3]] [[1], [2, 3]] [[1, 2], [3]] [[1, 2, 3]]
此外，您还需要执行import itertools以及from copy import deepcopy程序顶部的from copy import deepcopy 。
编辑：你给出的输出不清楚。 我推测你想要的是我给你的函数，但是你的输出还包含[[1,3],[2]] ，其中输出中的元素的顺序是不同的，不像其他的build议输出冒昧地假设你实际上不想[[1, 2], [3]] [[1, 2], 3] ）。
那就是说，我想你的意思是给出这样的结果：
[[1], [2], [3]] [[1], [2, 3]] [[1, 2], [3]] [[1, 2, 3]]
如果实际上是这样的话：
[[1], [2], [3]] [[1], [2, 3]] [[1, 2], [3]] [[1, 2, 3]] [[1], [3], [2]] [[1], [3, 2]] [[1, 3], [2]] [[1, 3, 2]] [[2], [1], [3]] [[2], [1, 3]] [[2, 1], [3]] [[2, 1, 3]] [[2], [3], [1]] [[2], [3, 1]] [[2, 3], [1]] [[2, 3, 1]] [[3], [1], [2]] [[3], [1, 2]] [[3, 1], [2]] [[3, 1, 2]] [[3], [2], [1]] [[3], [2, 1]] [[3, 2], [1]] [[3, 2, 1]]
那么你只需要为每个原始列表的3长度排列调用subgrups ，例如itertools.permutations(my_list, len(my_list))每个排列。
编辑：现在要坚持我的一个简短的基于itertools的解决scheme的承诺。 警告 – 这可能是无法读取和缓慢。
首先我们用这个replaceslice_by_lengths ：
def sbl(lengths, the_list): for index, length in enumerate(lengths): total_so_far = sum(lengths[:index]) yield the_list[total_so_far:total_so_far+length]
然后从这个答案我们得到我们的整数分区function：
def partition(number): return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}
这个函数实际上为我们获得了整数分区的所有排列，所以我们不需要
for each_partition in partitions: permed.append(set(itertools.permutations(each_partition, len(each_partition))))
了。 然而，它比我们以前慢得多，因为它是recursion的（我们正在用Python实现它）。
然后我们把它放在一起：
def subgrups(my_list): for each_tuple in partition(len(my_list)): yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))
或更less可读，但没有函数定义：
def subgrups(my_list): for each_tuple in (lambda p, f=lambda n, g: {(x,) + y for x in range(1, n) for y in g(nx, g)} | {(n,)}: f(p, f))(len(my_list)): yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))
这是一个函数定义和两行，与我原来所说的非常接近（尽pipe可读性和速度要慢得多）！
（因为问题最初要求find“所有子水印”，所以称为subgrups水印）
