且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

从Python中的整数列表确定所有可能产品的列表

更新时间: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)))