2
$\begingroup$

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
$\endgroup$
11
  • $\begingroup$ Why do you need the binary numbers to be consecutive? Just change it to $$\begin{array}{r|l-c} 0 & 00 & \emptyset \\ 0 & 01 & \{b_1\} \\ 0 & 10 & \{b_2\} \\ 0 & 11 & \text{invalid} \\ 1 & 00 & \{a\} \\ 1 & 01 & \{a,b_1\} \\ 1 & 10 & \{a,b_2\} \\ 1 & 11 & \text{invalid}\end{array}$$ $\endgroup$ Nov 18, 2021 at 23:54
  • $\begingroup$ @SlipEternal Then I could skip certain iterations but my question would be, how do I know which numbers to skip and thus also how many more steps I need. It looks like for the first register it is every 4 steps, which makes sense given that I need two bits to encode all states. Would I precalculate the invalid combinations? $\endgroup$
    – Mahoni
    Nov 18, 2021 at 23:59
  • $\begingroup$ Suppose you have this algorithm that encodes and decodes a particular combination. Questions: What would be the input to the decode algorithm? Just the encoded byte string? Or would you also be passing $n$? The various $k_i$? All elements of the component sets? What about for the encoding algorithm? What information is considered an input? $\endgroup$ Nov 19, 2021 at 0:11
  • $\begingroup$ My current approach uses a list numbers as input for the decode where each number represents the number of elements in a given set, that way I can directly select the element I want to include in the combination. For the encoding I just count up from 0 to $(k_1 + 1) \times \dots \times (k_2 + 1)$ $\endgroup$
    – Mahoni
    Nov 19, 2021 at 0:15
  • $\begingroup$ It sounds like your input is just a list of sets, not a multiset. Can we assume that the given sets have no elements in common? $\endgroup$
    – Karl
    Nov 19, 2021 at 0:20

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ "Efficient" is a complicated word. "Efficient" in what regard? Space consumption? Then yes, this algorithm is the most efficient. However, if it is computational complexity, this may not be more efficient. If space is cheap and computational power is expensive, the algorithm the OP was suggesting is on track to being more efficient. $\endgroup$ Nov 19, 2021 at 0:15
  • $\begingroup$ The number of operations required increases with each element that is true but I was also thinking that the cumulative product could be memorized in each step? $\endgroup$
    – Mahoni
    Nov 19, 2021 at 1:16
  • $\begingroup$ This is beautiful, just gave it a try. The time complexity is limited to something like: $(k_1 + 1) \times \dots \times (k_n + 1) \times n$. My approach was trying to make use of space but I think I lost time complexity again when I try to determine which numbers I have to increment and flow over I end up having to iterating the registers. I guess it's slightly more efficient because I don't have to iterate all of them but overall I love the simplicity this one produces. $\endgroup$
    – Mahoni
    Nov 19, 2021 at 2:20
  • $\begingroup$ Also, is there a name for this type of approach? I was trying to detect such a pattern when I was looking at the intervals at which the numbers are increased and different elements are picked from each set but I was wondering if this has a name $\endgroup$
    – Mahoni
    Nov 19, 2021 at 2:23
  • $\begingroup$ @Mahoni Best name I can think of is mixed radix numeral system. In your post, were trying binary, where each position is a power of $2$. My method is a numeral system where there is a $1$'s place, a $(k_1+1)$ place, a $(k_1+1)(k_2+1)$ place, etc. $\endgroup$ Nov 19, 2021 at 2:30
2
$\begingroup$

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')
$\endgroup$
4
  • $\begingroup$ I saw that, curious to how they implement that github.com/python/cpython/blob/main/Modules/… $\endgroup$
    – Mahoni
    Nov 19, 2021 at 1:06
  • $\begingroup$ I would assume the recursive approach is the brute force approach taking the longest in terms of time complexity? $\endgroup$
    – Mahoni
    Nov 19, 2021 at 1:22
  • 1
    $\begingroup$ No, the recursive approach is optimal (linear in the output size). $\endgroup$
    – Karl
    Nov 19, 2021 at 1:23
  • 1
    $\begingroup$ Generating a Cartesian product is only computationally expensive because of the large number of results; a reasonable "brute force" algorithm isn't doing any unnecessary work. $\endgroup$
    – Karl
    Nov 19, 2021 at 1:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .