patternMinor
What's the fastest known algorithm for generating $k$-subsets of an $n$-set?
Viewed 0 times
thewhatsubsetsalgorithmgeneratingknownfastestforset
Problem
We are given a set of $n$ elements and we'd like to generate all $k$-subsets of this set. For example, if $S=\{1,2,3\}$ and $k=2$, then the answer would be $\{1,2\}, \{1,3\}, \{2,3\}$ (order not important).
There are $\binom{n}{k}$ $k$-subsets of an $n$-set (by definition :-), which is $O(n^k)$ (although this is not tight). Obviously any algorithm for the problem will have to run in time $\Omega(\binom{n}{k})$.
What is the currently fastest known algorithm for this problem? Can the lower bound of $\binom{n}{k}$ actually be achieved (so that we have an essentially optimal algorithm)?
(Note: I reposted this from StackOverflow as the question seems better suited for CS StackExchange.)
There are $\binom{n}{k}$ $k$-subsets of an $n$-set (by definition :-), which is $O(n^k)$ (although this is not tight). Obviously any algorithm for the problem will have to run in time $\Omega(\binom{n}{k})$.
What is the currently fastest known algorithm for this problem? Can the lower bound of $\binom{n}{k}$ actually be achieved (so that we have an essentially optimal algorithm)?
(Note: I reposted this from StackOverflow as the question seems better suited for CS StackExchange.)
Solution
Knuth's Algorithm R Revolving-Door combinations is generally accepted as the current best for algorithms and time complexity for generating combinations.
Context
StackExchange Computer Science Q#54147, answer score: 4
Revisions (0)
No revisions yet.