How to generate all the possible combinations for a list of elements grouped in different sizes?

user_4105951 0
Viewed 91

I'm trying to create an algorithm that will return all the possible combinations from a list of elements (fruits in this example). The challenge is that the elements can be grouped in different sizes and the number of elements on the result list must be equal to n, where n is the list size. In short, all the elements must be on the final list.

Here is an example:

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']

We can quickly find all the combinations without repetition from size 0 to n as follows:

from itertools import combinations

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']
for L in range(0, len(fruits) + 1):
    for subset in combinations(fruits, L):
        print(subset)

The result:

()
('Apple',)
('Orange',)
('Banana',)
('Watermelon',)
('Apple', 'Orange')
('Apple', 'Banana')
('Apple', 'Watermelon')
('Orange', 'Banana')
('Orange', 'Watermelon')
('Banana', 'Watermelon')
('Apple', 'Orange', 'Banana')
('Apple', 'Orange', 'Watermelon')
('Apple', 'Banana', 'Watermelon')
('Orange', 'Banana', 'Watermelon')
('Apple', 'Orange', 'Banana', 'Watermelon')

However, what I'm looking for is different because all the elements must be present. Examples:

('Apple',) ('Orange',) ('Banana',) ('Watermelon',) is valid (1),(1),(1),(1)
('Apple',) ('Orange',) ('Banana', 'Watermelon') is valid (1),(1),(2)
('Apple',) ('Banana',) ('Orange', 'Watermelon') is valid (1),(1),(2)
('Apple',) ('Watermelon',) ('Orange', 'Banana') is valid (1),(1),(2)
('Apple',) ('Orange', 'Banana', 'Watermelon') is valid (1),(3)
...
('Apple', 'Orange') ('Banana', 'Watermelon') is valid (2),(2)
('Apple', 'Orange', 'Banana', 'Watermelon') is valid (4)

Is there an easy way to generate this in Python?

combinations python
1 Answers

You should take a look at the more-itertools library. And more particularly to the set_partitions method that should suits your needs.

from more-itertools import set_partitions

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']

for itm in set_partitions(fruits)):
    print(itm)

The ouput produce is :

[['Apple', 'Orange', 'Banana', 'Watermelon']]
[['Apple'], ['Orange', 'Banana', 'Watermelon']]
[['Apple', 'Orange'], ['Banana', 'Watermelon']]
[['Orange'], ['Apple', 'Banana', 'Watermelon']]
[['Apple', 'Orange', 'Banana'], ['Watermelon']]
[['Orange', 'Banana'], ['Apple', 'Watermelon']]
[['Apple', 'Banana'], ['Orange', 'Watermelon']]
[['Banana'], ['Apple', 'Orange', 'Watermelon']]
[['Apple'], ['Orange'], ['Banana', 'Watermelon']]
[['Apple'], ['Orange', 'Banana'], ['Watermelon']]
[['Apple'], ['Banana'], ['Orange', 'Watermelon']]
[['Apple', 'Orange'], ['Banana'], ['Watermelon']]
[['Orange'], ['Apple', 'Banana'], ['Watermelon']]
[['Orange'], ['Banana'], ['Apple', 'Watermelon']]
[['Apple'], ['Orange'], ['Banana'], ['Watermelon']]

EDIT:

And if you want all every combinations possible if you reorder your orignal list you can use the previous method in combination with the the permutations method of itertools with something like:

import itertools
from more_itertools import set_partitions

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']
output = list()

for x in itertools.permutations(fruits):
    output += list(set_partitions(x))
user_78516270
Related