Algorithm to generate all combinations of list of sets with up to one element per set

Question

For a given list of sets where the elements of the sets do not share any elements between the sets I want to compute all possible combinations where a combination can have up to one element per set. For example:

{{a}, {b1, b2}}

Would produce:

{ Ø, {a}, {b1}, {b2}, {a, b1}, {a, b2}}

I figured for any given multi-set with $n$ sets where set $n$ has $k_n$ elements there are: $$ (k_1 + 1) \times (k_2 + 1) + \dots + (k_n + 1) $$ possible combinations. My algorithmic approach so far has lead me to encode all possible combinations by keeping $n$ registers where each register can count up from $0$ to $k_n + 1$. For the example above this would look like this:

{0, 0} - Ø
{0, 1} - b1
{0, 2} - b2
{1, 0} - a
{1, 1} - a, b1
{1, 2} - a, b2

I then use those numbers to map them to the numbers in the sets. This works but in order to keep track of which number needs to flow over and which ones need resetting I have to go through each number in the register.

Is there a more efficient way, for instance encoding all different states into just one number? I tried doing this with a binary number and attempted to determine the element of the set with bitwise operations but ran into a problem where this example does not work:

0|00 - Ø
0|01 - b1
0|10 - b2
1|00 - a      <-- the consecutive number here would be 011
1|01 - a, b1
1|10 - a, b2

Answer 1

Yes, there is a more efficient way. Let $$ N=(k_1+1)\times\cdots\times(k_n+1) $$ be the number of possible selection. Given an integer $A\in \{0,1,\dots,N-1\}$, you can directly produce selection as follows. I will use $A\newcommand\per{\,\%\,}\per m $ to denote the remainder of $A$ divided by $m$, and $A\newcommand\quo{/\!\!/}\quo m$ to denote $\lfloor A/m\rfloor$. That is, $A\quo m$ is $A/m$ rounded down.

• Let $s_1=A\per (k_1+1)$. Note that there are $k_1+1$ possibilities for $s_1$, so $s_1$ defines our choice for the first set.

• Let $s_2=(A\quo (k_1+1))\per (k_2+1)$. Similarly, there are $(k_2+1)$ possible values for $s_2$, so $s_2$ determines our choice from the second set.

• Let $s_3=(A\quo [(k_1+1)(k_2+1)])\per (k_3+1)$. $s_3$ determines the choice from the third set.

And so on. In general, to compute $s_j$ from $A$, for each $j\in \{1,\dots,n\}$, you compute the product $(k_1+1)(k_2+1)\cdots(k_{j-1}+1)$ (when $j=1$, this is an empty product, equal to $1$), then compute the rounded-down-division of $A$ divided by that product, and finally set $s_j$ to be the result of that division modulo $(k_j+1)$.

This means that $A$ gives you a list $(s_1,s_2,\dots,s_n)$ which determines your selection completely. Every $A\in \{0,1,\dots,N-1\}$ gives a unique selection, no numbers are skipped.

Answer 2

This is a good task for a recursive algorithm: For each element $x$ of the first set, recursively iterate through the combinations of the remaining sets, prepending $x$ to each one.

There's also a Python library function itertools.product that does most of the work:

import itertools
mysets = [[None, "a"], [None, "b1", "b2"]]
for combi in itertools.product(*mysets):
    print(combi)

outputs:

(None, None)
(None, 'b1')
(None, 'b2')
('a', None)
('a', 'b1')
('a', 'b2')