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

Question

在 Python 2.7 中，我需要一种方法 returns list or tuple of int 所有可能的乘积。 IE。如果输入是 (2, 2, 3, 4)，那么我想要一个像

这样的输出

(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

包裹在 list or tuple 中。我认为使用 itertools 中的 combinations 可能会实现一个很好的实现，但我将不胜感激任何帮助。请注意，我只对不同的列表感兴趣，其中 int 的顺序不起作用。

编辑

进一步解释一些澄清。获取第一个输出列表。输入是 (2, 2, 3, 4)（总是）。然后我从列表中取出 2 和 2 out 并将它们相乘，所以现在我剩下一个列表 (3, 4, 4)。 3 和 4 来自输入，最后 4 来自产品。

我还没有尝试过任何东西，因为我无法绕过那种循环。但我无法停止思考这个问题，所以如果我得到建议，我会添加一些代码。

Answer 1

你的问题基本上是找到给定集合的所有子集（在你的情况下是多集）。一旦你有了子集，它就可以直接构建你所要求的输出。

对于集合 A 找到所有子集 [S0, S1, ..., Si]。对于每个子集Si，取(A - Si) | product(Si)，其中|是并集，-是集差。您可能对大小为 0 和 1 的子集不感兴趣，因此您可以排除这些。

查找子集是一个众所周知的问题，因此我相信您可以找到有关如何执行此操作的资源。请记住，有 N 个元素的集合有 2**N 个集合。

Answer 2

假设您有一个包含 4 个数字的向量（例如 (2,2,3,4)）。

您可以生成一个网格（如下所示）：

现在删除全部为“0”的行和只有一个“1”的行。

现在您可以用向量中的相应元素替换“1”。如果你的向量是 (2,2,3,4) 它变成：

尝试在 Python 中实现它。下面一段伪代码：

for i from 0 to 2^VECTOR_LEN:
    bin=convert_to_binary(i)
    if sum_binary_digit(bin) > 1:
       print(exec_moltiplication(bin,vector) 
       # if you want you can also use the bin vector as mask for the updating 
       # of your tuple of int with the result of the product and append it
       # in a list (as in your example).
       # For example if bin is (1 1 0 0) you can edit (2 2 3 4) in (4 3 4)
       # and append (4 3 4) inside the list or if it is (1 0 1 0) you can 
       # update (2 2 3 4) in (6 2 4)

其中：

向量：是包含数字的向量
VECTOR_LEN是向量的长度
convert_to_binary(num) 是一个将整数 (num) 转换为二进制的函数
sum_binary_digit(bin) 是一个对二进制数 (bin)
exec_multiplication(vector,bin) 输入向量 (vector) 和二进制 (bin) 和 returns 乘法的值。

Answer 3

您可以将其分解为三个步骤：

获取数字列表的所有排列
对于每个排列，创建所有可能的分区
对于分区中的每个子列表，计算乘积

对于排列，你可以使用itertools.permutations，但据我所知，分区没有内置函数，但写（或找）并不难：

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)]（data 为 182），但除非您的列表特别长，否则这应该问题不大。

我们可以把第二步和第三步结合起来；这样我们就可以在出现重复项时立即清除所有重复项：

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 重复项，可以通过在集合中排序和收集再次将其删除。结果同上

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)))

Answer 4

我不能给你算法（因为我自己也不知道），但是有一个库可以完成这个任务...... 看着你给定的输入数字，它们似乎是因子，所以如果我们将所有这些因子相乘，我们得到一个数字（比如 x），现在使用 sympy，我们可以获得该数字的所有除数：--

import numpy
ls = [2,2,3,4]

x = numpy.prod(ls)

from sympy import divisors
divisors_x = divisors(x)

给你！这是列表(divisors_x )

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

Determine list of all possible products from a list of integers in Python

python

algorithm

combinations

combinatorics