我有一个数组[1,2,3]
我想使用数组的所有元素进行所有可能的组合：
结果：
[[1], [2], [3]]
[[1,2], [3]]
[[1], [2,3]]
[[1,3], [2]]
[[1,2,3]]
问问题
21810 次
5 回答
65
既然这个好问题已经复活，这里有一个新的答案。
问题递归解决：如果你已经有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]]
于 2015-05-08T22:58:01.730 回答
11
与我建议的评论不同，我无法快速找到基于 itertools 的相对快速的解决方案！编辑：这不再是真的，我有一个相当短（但缓慢且不可读）的解决方案，主要使用 itertools，请参阅答案的结尾。这就是我得到的：
这个想法是我们找到所有整数的组合，加起来等于列表的长度，然后得到具有该长度切片的列表。
例如，对于长度为 3 的列表，组合或分区是 (3)、(2, 1)、(1, 2) 和 (1, 1, 1)。所以我们返回列表的前 3 项；前 2 个，然后是下一个 1；第一个 1，然后是下一个 2，第一个 1，然后是下一个，然后是下一个 1。
我从这里得到了整数分区的代码。但是，分区函数不会返回分区的所有排列（即对于 3，它只会返回 (3)、(2, 1) 和 (1, 1, 1)。所以我们需要调用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, 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
编辑：您给定的输出不清楚。我以为您想要我给您的功能，但您的输出还包含[[1,3],[2]]，其中输出中的元素的顺序不同，与您建议的输出的其余部分不同（我冒昧地假设您实际上[[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]]
然后，您只需要调用subgrups原始列表的每个 3 长度排列，例如在itertools.permutations(my_list, len(my_list)).
编辑：现在兑现我对基于简短itertools解决方案的承诺。警告 - 它可能既不可读又慢。
首先我们slice_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]
然后从这个答案我们得到我们的整数分区函数：
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))))
了。但是，它比我们以前的要慢得多，因为它是递归的（我们正在 Python 中实现它）。
然后我们把它放在一起：
def subgrups(my_list):
for each_tuple in partition(len(my_list)):
yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))
或者可读性较差，但没有函数定义：
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(n-x, 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))
这是一个函数定义和两行，与我最初所说的非常接近（尽管可读性低得多，速度也慢得多）！
（调用函数subgrups是因为问题最初要求查找“所有子组”）
于 2013-10-14T21:13:19.913 回答
6
考虑more_itertools.set_partitions。
给定
import more_itertools as mit
lst = [1, 2, 3]
代码
展平一系列k设置分区：
[part for k in range(1, len(lst) + 1) for part in mit.set_partitions(lst, k)]
输出
[((1, 2, 3),),
((1,), (2, 3)),
((2,), (1, 3)),
((3,), (1, 2)),
((1,), (2,), (3,))]
more_itertools是第三方包。通过安装> pip install more_itertools。
于 2019-07-20T23:31:10.330 回答
0
如果有人想在 JS 中使用它。这确实花了我一些时间来实施。我为 JS 的“价值与参考”而苦苦挣扎。
算法与上面解释的@alexis 相同。
函数 deepCopy 是克隆一个数组，而不是复制到一个数组。
function deepCopy(val){
return JSON.parse(JSON.stringify(val));
}
function partitions(arr) {
var results = [];
if (arr.length == 0) {
results.push([[]]);
return results;
}
if (arr.length == 1) {
results.push(new Array(arr));
return results;//[[[1]]]
}
var last = arr[arr.length - 1];
var sub = partitions(arr.slice(0, arr.length - 1));//remove the last item
//partitions(2) => [ [ [ 's1', 's2' ] ], [ [ 's1' ], [ 's2' ] ] ]
//val => [ [ 's1', 's2' ] ] or [ [ 's1' ], [ 's2' ] ]
//set => [ 's1', 's2' ] or [ 's1' ], [ 's2' ]
sub.map((partition) => {
//val => each partition
//1) insert the "last" into each set, together with the rest of sets in the same partition makes a new partition
partition.map((set) => {
//set=>each set of one particular partition
set.push(last);
results.push(deepCopy(partition));
set.pop();
});
//2), insert the "last" as a singlton set into the partition, make it a new partition
partition.push([last]);
results.push(deepCopy(partition));
partition.pop();
});
return results;
}
var arr = ["s1", "s2", "s3"];
const results = partitions(arr);
console.log(results);
输出：
[
[ [ 's1', 's2', 's3' ] ],
[ [ 's1', 's2' ], [ 's3' ] ],
[ [ 's1', 's3' ], [ 's2' ] ],
[ [ 's1' ], [ 's2', 's3' ] ],
[ [ 's1' ], [ 's2' ], [ 's3' ] ]
]
于 2021-03-29T13:01:06.497 回答
0
我将亚历克西斯的答案转换为使用循环而不是递归。代码不是那么容易理解，但现在也应该适用于非常大的集合：
def partition(collection: Sequence[T]) -> List[List[List[T]]]:
collection_except_last = reversed(collection[:-1])
only_last = list(collection[-1:])
# start with the partition for a 1-element collection and then add elements
partitions = [[only_last]]
for element in collection_except_last:
refined_partitions: List[List[List[T]]] = []
for partition_ in partitions:
# insert `element` in each of the subpartition's subsets
for n, subset in enumerate(partition_):
refined = partition_[:n] + [[element] + subset] + partition_[n + 1 :]
refined_partitions.append(refined)
# put `element` in its own subset
refined_partitions.append([[element]] + partition_)
partitions = refined_partitions
return partitions
于 2022-02-20T16:47:09.103 回答