[Small-cl-src-discuss] combinations and permutations (was: Small, occasionally handy piece of code)

[Steven E. Harris]

[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
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

-- 
Steven E. Harris        :: seharris at raytheon.com
Raytheon                :: http://www.raytheon.com