1
$\begingroup$

I have been looking at algorithms that allow you to generate $k$-combinations of a given string.

My question is that why isn't the algorithm used to generate power sets used to generate the combinations of a given string? That is, we can just use a binary counter of length $n$ with $k$ ones set to select $k$ elements from a length $n$ string. The method is very simple.

I mean, the power set can represent all $k$-combinations of the input. So why use complex algorithms like the ones described here (e.g., Gray codes)?

$\endgroup$
2
$\begingroup$

For concreteness, suppose you have a string $S$ of length $n = 10$. You want to generate all $k$-combinations of $S$ for some $k$, say $k = 3$. When you use a binary counter (using $n$ bits), you go through $2^n = 2^{10} = 1024$ values, corresponding to all possible subsets. On the other hand, there are only ${10 \choose 3} = 120$ possible 3-combinations choosable from $S$. So wouldn't it be nice if you could only perform 120 steps instead of 1024? I encourage you to play around with larger numbers, and consider how quickly these numbers actually grow.

There might also be other reasons to consider e.g., Gray codes. Some algorithms have particular properties that might be crucial for certain applications. For instance, we might want that there's exactly one change between two adjacent combinations, or so on.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for that answer and editing my question. Yes you did capture my actual intention. I thought I was never going to get an answer to the problem. Just to get it straight, it is then POSSIBLE to generate combinations with a binary counter, right ? Its just not very efficient. Am I correct ? $\endgroup$ – Kramer786 Jun 11 '16 at 9:47
  • $\begingroup$ @Kramer786 Yes, that's correct. $\endgroup$ – Juho Jun 11 '16 at 10:42

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.