snippetMinor
Algorithm to generate combinations of n elements from n sets of m elements
Viewed 0 times
elementscombinationssetsalgorithmgeneratefrom
Problem
Suppose I have 3 sets of 2 elements:
What algorithm can I use to generate all combinations. Keep in mind that I'm looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I'm looking for an algorithm to actually generate the combinations, not just count them.
[A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of the algorithm would be:[A, C, E], [A, C, F], [A, D, E], [A, D, F], [B, C, E], [B, C, F], [B, D, E], [B, D, F]What algorithm can I use to generate all combinations. Keep in mind that I'm looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I'm looking for an algorithm to actually generate the combinations, not just count them.
Solution
If you have $n$ sets of $k$ elements, your problem is equivalent to that of generating all numbers with up to $n$ digits in base $k$ (where the $i$-th digit of a number represents the index of the element to select from the $i$-th group).
This can easily be done by starting from the number $(00\dots000)_k$ and iteratively adding $1$. Let $d_i$ be the $i$-th least significant digit. Start from $i=1$ and do the following: if $d_i < k-1$ the next number is obtained by increasing $d_i$ by $1$. Otherwise set $d_i =0$, increase $i$ by $1$ and repeat. When $i$ reaches $n+1$ you know that you have already generated all the numbers and you can stop.
This procedure takes $O(k^n)$ time (assuming that $k$ fits in a constant number of memory words). To see this notice that you need to update $d_1$ every time you increment the number, $d_2$ changes only every $k$ increments, etc. In general $d_i$ changes every $k^{i-1}$ increments.
Since the total number of increments is $k^n$, the total number of operations is:
$$
O\left(\sum_{i=1}^n \frac{k^n}{k^{i-1}} \right) =
O\left(\sum_{i=1}^n k^{n-i+1} \right) =
O\left(k \cdot \sum_{i=0}^{n-1} k^i \right) =
O\left(k \cdot \frac{k^n - 1}{k-1} \right) =
O(k^n).
$$
This time complexity is asymptotically optimal because $\Omega(k^n)$ is a trivial lower bound (as there are $k^n$ distinct combinations to return).
A pseudocode:
This can easily be done by starting from the number $(00\dots000)_k$ and iteratively adding $1$. Let $d_i$ be the $i$-th least significant digit. Start from $i=1$ and do the following: if $d_i < k-1$ the next number is obtained by increasing $d_i$ by $1$. Otherwise set $d_i =0$, increase $i$ by $1$ and repeat. When $i$ reaches $n+1$ you know that you have already generated all the numbers and you can stop.
This procedure takes $O(k^n)$ time (assuming that $k$ fits in a constant number of memory words). To see this notice that you need to update $d_1$ every time you increment the number, $d_2$ changes only every $k$ increments, etc. In general $d_i$ changes every $k^{i-1}$ increments.
Since the total number of increments is $k^n$, the total number of operations is:
$$
O\left(\sum_{i=1}^n \frac{k^n}{k^{i-1}} \right) =
O\left(\sum_{i=1}^n k^{n-i+1} \right) =
O\left(k \cdot \sum_{i=0}^{n-1} k^i \right) =
O\left(k \cdot \frac{k^n - 1}{k-1} \right) =
O(k^n).
$$
This time complexity is asymptotically optimal because $\Omega(k^n)$ is a trivial lower bound (as there are $k^n$ distinct combinations to return).
A pseudocode:
A = An array of n integer elements, indexed from 1;
for i=1,...,n: A[i]=0;
while true:
//A contains a n digit number in base k. Do something with it
i = 1;
while in:
return; //We have already seen all n-digits numbers in base k
else:
A[i]=A[i]+1;Code Snippets
A = An array of n integer elements, indexed from 1;
for i=1,...,n: A[i]=0;
while true:
//A contains a n digit number in base k. Do something with it
i = 1;
while i<=n and A[i]==k-1:
A[i]=0;
i=i+1;
if i>n:
return; //We have already seen all n-digits numbers in base k
else:
A[i]=A[i]+1;Context
StackExchange Computer Science Q#125752, answer score: 3
Revisions (0)
No revisions yet.