mr.bjerre - 1 year ago 56

Python Question

In Python 2.7 I need a method that returns all possible products of a

`list or tuple of int`

`(2, 2, 3, 4)`

- , 2 * 2 = 4
`(3, 4, 4)`

- , 2 * 3 = 6
`(2, 4, 6)`

- , 2 * 4 = 8
`(2, 3, 8)`

- , 2 * 2 = 4
`(3, 4, 4)`

- , 3 * 4 = 12
`(2, 2, 12)`

- , 2 * 3 * 4 = 24
`(2, 24)`

- , 2 * 2 * 4 = 16
`(3, 16)`

- , 2 * 2 * 3 = 12
`(4, 12)`

- , 2 * 2 * 3 * 4 = 48
`(48)`

wrapped up in a

`list or tuple`

`itertools`

`int`

EDIT

Some futher explanation for some clarification. Take the first output list. Input is

`(2, 2, 3, 4)`

`(3, 4, 4)`

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.

Answer Source

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