I am looking for the canonical implementation of the "k-combinations with repetition" algorithm.

Simple Example:

Input: "ABC" (choose 2)

['AA', 'AB', 'AC', 'BB', 'BC', 'CC']

I have a recursive implementation, I'm looking for the performance optimized state of the art version. Usually people mention Knuth for this, but I haven't seen a specific reference to Vol 4a or otherwise for this particular one. Not to say it isn't there, just haven't found any references to it.

Where might I look further into this?

  • $\begingroup$ Consult Section 7 of Knuth's Art of Computer Programming. See for example this (other parts are in the same directory). $\endgroup$ – Yuval Filmus Aug 1 '17 at 6:34

Your Answer

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

Browse other questions tagged or ask your own question.