[I apologize for posting this article incorrectly first to the "code" list rather than the "discuss" list.]

"Steven E. Harris" seharris@raytheon.com writes:

I wrote one a while ago that may cons less because it requires use of vectors to represent the sequences.

Following up to myself, if you're interested, I also have similar code to produce permutations from a source vector, though the permutation algorithm operates destructively in-place on the source sequence.

It's been about six months since I was doing the analysis for this code, but I recall some interesting interdependencies between combinations and permutations. Unfortunately my notes are at home right now.

For example, one can compute /how many/ permutations exist for a full draw from a set (n!), or how many permutations exist for a draw k from a set (n!/(n - k)!), but computing how many combinations exist for any draw k is dependent upon the related permutation count (P/k!).¹

However, to actually come up with the /specific/ permutations and combinations, the dependency is reversed. One can come up with combinations in any draw k independently. One can also come up with permutations for a full draw independently. But to come up with the permutations for some draw k, one must first generate the combinations of draw k, then permute each of those combinations as a full draw. The apparent independence of the full draw permutations is due to there being only one combination to permute for a full draw.

Footnotes: ¹ http://www.themathpage.com/aPreCalc/permutations-combinations.htm