Skip to content
Advertisement

How to create the set of all possible sets formed by selecting 0 or 1 elements from n lists

Ama

As an example, say I have the following six lists:

[2], [2,3], [4], [1,2], [2], [1,4]

I want to make a new list that has either 0 or 1 elements from each of these lists. One such list could be [2,2,4,1,2,1] which is made by selecting the first element from each list. Another such list could be [2,3,2,2,4] which is made by selecting the last element from each list. Another could be [2,4,1,2] which has no elements from the first and last lists. How can I form a list of lists (in python) that has all possible lists made from selecting either 0 or 1 elements from these six lists? Any help would be greatly appreciated!

Advertisement

Answer

You want the product of all the lists. To include the case where you select zero elements from any given list, you can add None to all the lists, and then remove None elements before you yield a selection.

This assumes you don’t have any Nones in the original lists. If you do, you can replace the Nones in this logic with some dummy value that your lists won’t contain.

import itertools

def optional_product(*iterables, dummy=None):
    iterables = [itertools.chain(itbl, [dummy]) for itbl in iterables]

    for selection in itertools.product(*iterables):
        sel = [s for s in selection if s != dummy]
        yield sel

Note: To support iterables other than lists, I use itertools.chain to “append” a None to each input iterable.

To run this:

for sel in optional_product([2], [2,3], [4], [1,2], [2], [1,4]):
    print(sel)

which prints:

[2, 2, 4, 1, 2, 1]
[2, 2, 4, 1, 2, 4]
[2, 2, 4, 1, 2]
[2, 2, 4, 1, 1]
[2, 2, 4, 1, 4]
[2, 2, 4, 1]
[2, 2, 4, 2, 2, 1]
[2, 2, 4, 2, 2, 4]
[2, 2, 4, 2, 2]
[2, 2, 4, 2, 1]
[2, 2, 4, 2, 4]
[2, 2, 4, 2]
[2, 2, 4, 2, 1]
[2, 2, 4, 2, 4]
[2, 2, 4, 2]
[2, 2, 4, 1]
[2, 2, 4, 4]
[2, 2, 4]
[2, 2, 1, 2, 1]
[2, 2, 1, 2, 4]
[2, 2, 1, 2]
[2, 2, 1, 1]
[2, 2, 1, 4]
[2, 2, 1]
[2, 2, 2, 2, 1]
[2, 2, 2, 2, 4]
[2, 2, 2, 2]
[2, 2, 2, 1]
[2, 2, 2, 4]
[2, 2, 2]
[2, 2, 2, 1]
[2, 2, 2, 4]
[2, 2, 2]
[2, 2, 1]
[2, 2, 4]
[2, 2]
[2, 3, 4, 1, 2, 1]
[2, 3, 4, 1, 2, 4]
[2, 3, 4, 1, 2]
[2, 3, 4, 1, 1]
[2, 3, 4, 1, 4]
[2, 3, 4, 1]
[2, 3, 4, 2, 2, 1]
[2, 3, 4, 2, 2, 4]
[2, 3, 4, 2, 2]
[2, 3, 4, 2, 1]
[2, 3, 4, 2, 4]
[2, 3, 4, 2]
[2, 3, 4, 2, 1]
[2, 3, 4, 2, 4]
[2, 3, 4, 2]
[2, 3, 4, 1]
[2, 3, 4, 4]
[2, 3, 4]
[2, 3, 1, 2, 1]
[2, 3, 1, 2, 4]
[2, 3, 1, 2]
[2, 3, 1, 1]
[2, 3, 1, 4]
[2, 3, 1]
[2, 3, 2, 2, 1]
[2, 3, 2, 2, 4]
[2, 3, 2, 2]
[2, 3, 2, 1]
[2, 3, 2, 4]
[2, 3, 2]
[2, 3, 2, 1]
[2, 3, 2, 4]
[2, 3, 2]
[2, 3, 1]
[2, 3, 4]
[2, 3]
[2, 4, 1, 2, 1]
[2, 4, 1, 2, 4]
[2, 4, 1, 2]
[2, 4, 1, 1]
[2, 4, 1, 4]
[2, 4, 1]
[2, 4, 2, 2, 1]
[2, 4, 2, 2, 4]
[2, 4, 2, 2]
[2, 4, 2, 1]
[2, 4, 2, 4]
[2, 4, 2]
[2, 4, 2, 1]
[2, 4, 2, 4]
[2, 4, 2]
[2, 4, 1]
[2, 4, 4]
[2, 4]
[2, 1, 2, 1]
[2, 1, 2, 4]
[2, 1, 2]
[2, 1, 1]
[2, 1, 4]
[2, 1]
[2, 2, 2, 1]
[2, 2, 2, 4]
[2, 2, 2]
[2, 2, 1]
[2, 2, 4]
[2, 2]
[2, 2, 1]
[2, 2, 4]
[2, 2]
[2, 1]
[2, 4]
[2]
[2, 4, 1, 2, 1]
[2, 4, 1, 2, 4]
[2, 4, 1, 2]
[2, 4, 1, 1]
[2, 4, 1, 4]
[2, 4, 1]
[2, 4, 2, 2, 1]
[2, 4, 2, 2, 4]
[2, 4, 2, 2]
[2, 4, 2, 1]
[2, 4, 2, 4]
[2, 4, 2]
[2, 4, 2, 1]
[2, 4, 2, 4]
[2, 4, 2]
[2, 4, 1]
[2, 4, 4]
[2, 4]
[2, 1, 2, 1]
[2, 1, 2, 4]
[2, 1, 2]
[2, 1, 1]
[2, 1, 4]
[2, 1]
[2, 2, 2, 1]
[2, 2, 2, 4]
[2, 2, 2]
[2, 2, 1]
[2, 2, 4]
[2, 2]
[2, 2, 1]
[2, 2, 4]
[2, 2]
[2, 1]
[2, 4]
[2]
[3, 4, 1, 2, 1]
[3, 4, 1, 2, 4]
[3, 4, 1, 2]
[3, 4, 1, 1]
[3, 4, 1, 4]
[3, 4, 1]
[3, 4, 2, 2, 1]
[3, 4, 2, 2, 4]
[3, 4, 2, 2]
[3, 4, 2, 1]
[3, 4, 2, 4]
[3, 4, 2]
[3, 4, 2, 1]
[3, 4, 2, 4]
[3, 4, 2]
[3, 4, 1]
[3, 4, 4]
[3, 4]
[3, 1, 2, 1]
[3, 1, 2, 4]
[3, 1, 2]
[3, 1, 1]
[3, 1, 4]
[3, 1]
[3, 2, 2, 1]
[3, 2, 2, 4]
[3, 2, 2]
[3, 2, 1]
[3, 2, 4]
[3, 2]
[3, 2, 1]
[3, 2, 4]
[3, 2]
[3, 1]
[3, 4]
[3]
[4, 1, 2, 1]
[4, 1, 2, 4]
[4, 1, 2]
[4, 1, 1]
[4, 1, 4]
[4, 1]
[4, 2, 2, 1]
[4, 2, 2, 4]
[4, 2, 2]
[4, 2, 1]
[4, 2, 4]
[4, 2]
[4, 2, 1]
[4, 2, 4]
[4, 2]
[4, 1]
[4, 4]
[4]
[1, 2, 1]
[1, 2, 4]
[1, 2]
[1, 1]
[1, 4]
[1]
[2, 2, 1]
[2, 2, 4]
[2, 2]
[2, 1]
[2, 4]
[2]
[2, 1]
[2, 4]
[2]
[1]
[4]
[]

The last value yielded is the case where zero elements are selected from all lists. If you don’t want this, you can simply yield sel only when sel is non-empty.

To obtain a list of lists containing all selections, just do list(optional_product(...))

Advertisement