mr.bjerre mr.bjerre - 2 months ago 7
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.

Answer

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