All possible summations within a list

Question

I have a list of elements of a custom class Fun. What I want is to generate all possible summations of this list. For example, if I have the list [Fun1, Fun2, Fun3], I want to generate the list:

[[Fun1 + Fun2, Fun3], [Fun1 + Fun3, Fun2], [Fun2 + Fun3, Fun1], [Fun1, Fun2, Fun3], [Fun1 + Fun2 + Fun3]]

This should generate for longer lists but I know that all elements of my list are of the same type, a custom class named Fun. And it is possible to sum elements of the class Fun, I already implemented the way they are supposed to be summed.

I have tried several ways to generate this list of possible summations, mainly using variations of itertools.combinations and itertools.product but without success. I have also tried list comprehension (things like [[x + y for x in my_list if x != y] for y in my_list]) without success. Usually, I get bugs like "type Fun is not iterable" or my output is only one element (the original one).

The expected output seems inconsistent. What about `[[Fun1 + Fun2, Fun3], [Fun1 + Fun3, Fun2], [Fun2 + Fun3, Fun1], [Fun1 + Fun2 + Fun3, 0]]`? — Mateen Ulhaq, Sep 01 '23 at 11:18
See also: `itertools.permutations` and `itertools.combinations`. — Mateen Ulhaq, Sep 01 '23 at 11:20
This answer should apply to your question: https://stackoverflow.com/a/65854062/5237560 — Alain T., Sep 01 '23 at 15:11
I don't need all my sublists to be of the same size, all I need is for my Fun_i to be all represented once in each sublist. — Sofiane, Sep 01 '23 at 18:41

score 1 · Answer 1 · answered Sep 01 '23 at 11:27

It's very easy if you install the more-itertools package.

So, first of all, install it:

>>> pip install more-itertools

Now you can do what you asked very easily. Since I don't have your definition of class Fun, let me do an example with ints. Please keep in mind that your class must support the summation of elements. That part is up to you to define.

from more_itertools import set_partitions

lst = [1, 2, 3]

partitions = [
    part
    for k in range(1, len(lst) + 1)
    for part in set_partitions(lst, k)
]

partition_sums = [
    [sum(p) for p in part]
    for k in range(1, len(lst) + 1)
    for part in set_partitions(lst, k)
]

>>> partitions
[[[1, 2, 3]], [[1], [2, 3]], [[1, 2], [3]], [[2], [1, 3]], [[1], [2], [3]]]
>>> partition_sums
[[6], [1, 5], [3, 3], [2, 4], [1, 2, 3]]

If you don't want to install that package, other ways to compute set partitions in python can be found here: Set partitions in Python

All possible summations within a list

1 Answers1