更新时间:2023-01-11 21:48:45
您可以将其分解为三个步骤:
You can break this down into three steps:
对于排列,您可以使用 itertools.permutations
,但是据我所知,分区没有内置函数,但这并不难编写(或查找):
For the permutations, you can use itertools.permutations
, but as far as I know, there is no builtin function for partitions, but that's not too difficult to write (or to find):
def partitions(lst):
if lst:
for i in range(1, len(lst) + 1):
for p in partitions(lst[i:]):
yield [lst[:i]] + p
else:
yield []
对于类似(1,2 ,3,4)
,这将生成 [(1),(2),(3),(4)]
, [(1) ,(2),(3,4)]
, [(1),(2,3),(4)]
, [(1),(2,3,4)]
,依此类推,例如 [(1,3),(2),(4)]
;这就是为什么我们还需要排列的原因。但是,对于所有排列,这将创建许多实际上是重复的分区,例如 [(1,2 ,,(3,4)]
和 [(4,3),(1,2)]
(对于您的数据
为182),但是除非您的列表特别长,否则
For a list like (1,2,3,4)
, this will generate [(1),(2),(3),(4)]
, [(1),(2),(3,4)]
, [(1),(2,3),(4)]
, [(1),(2,3,4)]
, and so on, but not, e.g. [(1,3),(2),(4)]
; that's why we also need the permutations. However, for all the permutations, this will create many partitions that are effectively duplicates, like [(1,2),(3,4)]
and [(4,3),(1,2)]
(182 for your data
), but unless your lists are particularly long, this should not be too much of a problem.
我们可以将第二步和第三步结合起来;这样,我们就可以清除所有重复项:
We can combine the second and third step; this way we can weed out all the duplicates as soon as they arise:
data = (2, 2, 3, 4)
res = {tuple(sorted(reduce(operator.mul, lst) for lst in partition))
for permutation in itertools.permutations(data)
for partition in partitions(permutation)}
之后, res
为 {(6,8),(2,4,6),(2,2,3,4),(2,2,12),(48,),(3,4,4),(4 ,12),(3,16),(2,24),(2,3,8)}
或者,您可以将其全部组合在一个稍微复杂一点的算法中。由于您的数据集中有两个 2
,这仍然会生成 some 重复项,可以通过排序和收集再次将其删除。结果与上面相同。
Alternatively, you can combine it all in one, slightly more complex algorithm. This still generates some duplicates, due to the two 2
in your data set, that can again be removed by sorting and collecting in a set. The result is the same as above.
def all_partitions(lst):
if lst:
x = lst[0]
for partition in all_partitions(lst[1:]):
# x can either be a partition itself...
yield [x] + partition
# ... or part of any of the other partitions
for i, _ in enumerate(partition):
partition[i] *= x
yield partition
partition[i] //= x
else:
yield []
res = set(tuple(sorted(x)) for x in all_partitions(list(data)))