Combinatorial mathematics deals with, among other things, functions dealing with calculating or displaying the number of combinations one can have of 10 things taken two at a time, etc. then help me word it.

[AM] In school I learned the following meanings for the expressions "permutation", "variation" and "combination":

permutation: An ordering of a set of N elements where the order is significant.
variation: A subset of M elements out of N elements (M lower or equal N) where the order is significant.
combination: A subset of M elements out of N elements where the order is ''not'' significant.

Simple formulae exist to calculate the number of permutations, variations and combinations, given N and M:

Number of permutations: N!  (N faculty)
Number of variations:   N!/M!
Number of combinations: N!/M!(N-M)!

So, the procedure "permutations" below is actually a procedure to return the variations.
But if M == N, there is no difference.

----
This came up on c.l.t so searching around the wiki I found some info at[Power set of a list] as well, but when searching, I found this page first (as I assume others would) so here is a copy stolen from there (was subsets2 on that page):


 proc combinations { list size } {
     if { $size == 0 } {
         return [list [list]]
     }
     set retval {}
     for { set i 0 } { ($i + $size) <= [llength $list] } { incr i } {
         set firstElement [lindex $list $i]
         set remainingElements [lrange $list [expr { $i + 1 }] end]
         foreach subset [combinations $remainingElements [expr { $size - 1 }]] {
             lappend retval [linsert $subset 0 $firstElement]
         }
     }
     return $retval
 }

If order of elements is meaningfull then you would want permutations so here is a proc to do that:

 proc permutations { list size } {
     if { $size == 0 } {
         return [list [list]]
     }
     set retval {}
     for { set i 0 } { $i < [llength $list] } { incr i } {
         set firstElement [lindex $list $i]
         set remainingElements [lreplace $list $i $i]
         foreach subset [subsets2 $remainingElements [expr { $size - 1 }]] {
             lappend retval [linsert $subset 0 $firstElement]
         }
     }
     return $retval
 }

And if you do want the power set you could use the nice version by [Kevin Kenny] presented on that page or make use of the combinations proc above:

 proc powerset {list} {
    for {set i 0} {$i <= [llength $list]} {incr i} {
        lappend ret [combinations $list $i]
    }
    return $ret
 }


----
See also

   * [Cartesian product of a list of lists] - little actual math here, but involves displaying one kind of combination
   * [Binomial coefficients] includes not only ''C(n,k)'' but also an implementation of the Gamma function.

----
[Category Mathematics]