猿问
下载APP

在Python中设置分区

在Python中设置分区

我有一个数组 [1,2,3]


我想使用数组的所有元素进行所有可能的组合:


结果:


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

[[1,2], [3]]

[[1], [2,3]]

[[1,3], [2]]

[[1,2,3]]


陪伴而非守候
浏览 51回答 3
3回答

慕慕森

由于这个好问题已经复活,这是一个新的答案。这个问题是递归解决的:如果你已经有一个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 ] ] + smallersomething = 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]]

喵喵时光机

与我建议的评论不同,我无法快速找到基于itertools的相对快速的解决方案!编辑:这不再是真的,我有一个相当短的(但缓慢且不可读)的解决方案,主要使用itertools,请参阅答案的结尾。这就是我得到的:我们的想法是,我们找到加起来列表长度的所有整数组合,然后获得具有该长度的切片的列表。例如,对于长度为3的列表,组合或分区是(3),(2,1),(1,2)和(1,1,1)。所以我们返回列表的前3项; 前2然后下1; 第一个然后是下一个2和第一个1,然后是下一个1,然后是下一个1。我从这里得到了整数分区的代码。但是,分区函数不会返回分区的所有排列(即对于3,它只返回(3),(2,1)和(1,1,1)。所以我们需要调用itertools.permutations每个分区。然后,我们需要删除重复的-就像permutations([1, 2, 3])IS [[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是因为最初要求查找“所有子项目”的问题)

慕圣8478803

考虑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。
打开App,查看更多内容
随时随地看视频慕课网APP
我要回答