mr.bjerre - 1 month ago 5x
Python Question

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

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

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

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:

• get all the permutations of the list of numbers
• for each of those permutations, create all the possible partitions
• for each sublist in the partitions, calculate the product

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 []
``````

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

Afterwards, `res` is `{(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)}`

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