从Python中的整数列表确定所有可能产品的列表 [英] Determine list of all possible products from a list of integers in Python
问题描述
在Python 2.7中，我需要一个返回列表或int 元组的所有可能乘积的方法。就是如果输入是（2，2，3，4），那么我想要的输出是
In Python 2.7 I need a method that returns all possible products of a list or tuple of int. Ie. if input is (2, 2, 3, 4), then I'd want a output like
-
（3，4，4），2 * 2 = 4 -
（ 2，4，6），2 * 3 = 6 -
（2，3，8），2 * 4 = 8 -
（3，4，4），2 * 2 = 4 -
（2，2，12），3 * 4 = 12 -
（2， 24），2 * 3 * 4 = 24 -
（3，16），2 * 2 * 4 = 16 -
（4，12），2 * 2 * 3 = 12 -
（48），2 * 2 * 3 * 4 = 48
(3, 4, 4), 2 * 2 = 4(2, 4, 6), 2 * 3 = 6(2, 3, 8), 2 * 4 = 8(3, 4, 4), 2 * 2 = 4(2, 2, 12), 3 * 4 = 12(2, 24), 2 * 3 * 4 = 24(3, 16), 2 * 2 * 4 = 16(4, 12), 2 * 2 * 3 = 12(48), 2 * 2 * 3 * 4 = 48
包裹在列表或元组中。我认为使用组合来自 itertools ，但我将不胜感激。请注意，我只对不同的列表感兴趣，其中 int 的顺序不起作用。
wrapped up in a list or tuple. I figure that a nice implementation is probably possible using combinations from itertools, but I'd appreciate any help. Note that I am only interested in distinct lists, where order of int plays no role.
EDIT
一些进一步的解释。取得第一个输出列表。输入为（2，2，3，4）（始终）。然后我从列表中取出2和2 并将它们相乘，所以现在剩下列表（3，4，4）。输入中的3和4，产品中的最后4个。
Some futher explanation for some clarification. Take the first output list. Input is (2, 2, 3, 4) (always). Then I take 2 and 2 out of the list and multiply them, so now I am left with a list (3, 4, 4). 3 and 4 from the input and the last 4 from the product.
我还没有尝试过任何东西，因为我无法绕这种循环旋转头。但是我不能停止考虑这个问题，因此，如果确实有建议，我将添加一些代码。
I haven't tried anything yet since I just can't spin my head around that kind of loop. But I can't stop thinking about the problem, so I'll add some code if I do get a suggestion.
推荐答案
您可以将其分解为三个步骤：
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)))
这篇关于从Python中的整数列表确定所有可能产品的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
