1
$\begingroup$

I would like to estimate complexity in space and time of generating every combination of every size for a given sequence.

Exemple :

 seq = [1,2,3]
 combinations = [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

From what i know, for a given sequence of size n and a fixed combination size k, the number of combination generated is ${n}\choose{k}$, so i suppose than complexity in time and space is $O({{n}\choose{k}})$.

What we want is the sum for every value of $k$, $O({\sum_{i=1}^n{{n}\choose{i}}})$

I know that for a sum the complexity equals to the most complex element of the sum.

For the binomial coefficient, if n is even, the biggest one will be $n \choose \frac{n}{2}$

So i can put a an upper born as $O(n.{n \choose \frac{n}{2}})$

Is there a more precise way to determine the complexity of this operation ?

$\endgroup$
  • $\begingroup$ It seems that you are trying to generate all the non-empty subsets of given set $S$. If $S$ has $n$ elements, there're $2^n - 1$ non-empty different subsets, so a lower bound would be $2^n - 1$. $\endgroup$ – sel Jul 20 '17 at 9:14
  • 1
    $\begingroup$ The number of subsets of a set of size $n$ is $2^n$. Depending on your computation model, you should be able to generate all sets in $O(n2^n)$ or better. $\endgroup$ – Yuval Filmus Jul 20 '17 at 10:18
  • $\begingroup$ Maybe this helps en.wikipedia.org/wiki/… $\endgroup$ – adrianN Jul 20 '17 at 10:29
  • $\begingroup$ Maybe this would help. $\endgroup$ – Evil Jul 21 '17 at 3:14
2
$\begingroup$

Each element in the sequence is part of the combination or not (a binary choice). Since there are $n$ elements, this gives $2^n$ possible combinations.

Using a gray code to iterate over the elements we can make sure that we iterate over every possible combination by only putting in or taking out a single element every time.

Assuming your elements are numbered $1\dots n$ we can use the following algorithm. If our current combination $C_k$ contains an even amount of elements, toggle element $1$ to get $C_{k+1}$. Otherwise, toggle element $\min(C_k)+1$ to get $C_{k+1}$.

Starting from the empty combination $\{\}$ we get:

\begin{matrix} \{\} & \text{even} & \text{toggle $1$}\\ \{1\} & \text{odd} & \text{toggle $\min(\{1\}) + 1$}\\ \{1, 2\} & \text{even} & \text{toggle $1$}\\ \{2\} & \text{odd} & \text{toggle $\min(\{2\}) + 1$}\\ \{2, 3\} & \text{even} & \text{toggle $1$}\\ \{1, 2, 3\} & \text{odd} & \text{toggle $\min(\{1, 2, 3\}) + 1$}\\ \{1, 3\} & \text{even} & \text{toggle $1$}\\ \{3\} & \text{odd} & \text{toggle $\min(\{3\}) + 1$}\\ \cdots & \cdots &\cdots \end{matrix}

By separately storing whether we are currently even/odd and flipping it, and storing our combination in sorted order we can always get to the next combination in $O(1)$ time. So it simply takes $O(2^n)$ time to generate all combinations.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.