[Small-cl-src-discuss] combinations and permutations (was: Small, occasionally handy piece of code)
Steven E. Harris
seharris at raytheon.com
Fri Jul 9 17:57:36 UTC 2004
[I apologize for posting this article incorrectly first to the "code"
list rather than the "discuss" list.]
"Steven E. Harris" <seharris at 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
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.
Steven E. Harris :: seharris at raytheon.com
Raytheon :: http://www.raytheon.com
More information about the Small-cl-src-discuss