The combinatorial number system shows that there is a bijection between the natural numbers less than $n \choose k$ and $n\choose k$ combinations. There is a greedy algorithm for unranking combinations, which one may calculate the worst-case run time for. I'm curious: is this the fastest algorithm in terms of asymptotic worst-case run time? If not, what is the fastest algorithm, and what is the worst-case run time?

  • $\begingroup$ do you know the current complexity of this greedy algorithm? If so, please provide a reference for it. $\endgroup$ Commented Apr 4, 2023 at 21:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.