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!/(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.

(Note: small correction in "permutations" - "subsets2" was called instead of "permutations")

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

[KPV] here's another version of combinations that I came up with before I found this page. It 
seems to be quite a bit faster (6 versus 24 seconds for the 184,756 elements when N=20, M=10). It 
uses an extra optional argument (prefix) to hold partial solutions, which, I think, leads
to a clearer solution:
 
 proc combinations2 {myList size {prefix {}}} {
    ;# End recursion when size is 0 or equals our list size
    if {$size == 0} {return [list $prefix]}
    if {$size == [llength $myList]} {return [list [concat $prefix $myList]]}

    set first [lindex $myList 0]
    set rest [lrange $myList 1 end]

    ;# Combine solutions w/ first element and solutions w/o first element
    set ans1 [combinations2 $rest [expr {$size-1}] [concat $prefix $first]]
    set ans2 [combinations2 $rest $size $prefix]
    return [concat $ans1 $ans2]
 }


If order of elements is meaningful 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 [permutations $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
 }

----
Frans Houweling: In generating k-subsets both combinations2 and the iterative solution presented in [Power set of a list] ate up all my memory. So here is a workaround.
    #
    # nextK
    # Returns next k-subset given a current k-subset in ordinal representation.
    # For example the 126 4-subsets of a set of 9 start with {1 2 3 4} and end
    # with {6 7 8 9}.
    # Values copied to and fro between list and array to avoid lreplace hassle.
    #
    proc nextK {n k {current {}}} {
        if {![llength $current]} {
    	   for {set i 1} {$i <= $k} {incr i} {
    	      set c($i) $i
    	   }
        } elseif {[llength $current] != $k} {
    	   error "current combination not a k-subset"
        } else {
    	    for {set i 1; set j 0} {$i <= $k} {incr i; incr j} {
    	       set c($i) [lindex $current $j]
    	       if {![string is integer -strict $c($i)] || $c($i) == 0} {
    		  error "only ordinal numbers 1..n allowed"
    	       }
    	    }
    	    set ptr $k
    	    while {$ptr > 0 && $c($ptr) == [expr $n - $k + $ptr]} {
    	       incr ptr -1
    	    }
    	    if {$ptr == 0} {
    	      return {}
    	    }
    	    incr c($ptr)
    	    for {set i [expr $ptr + 1]} {$i <= $k} {incr i} {
    	       set c($i) [expr $c([expr $i - 1]) + 1]
    	    }
        }
        set cL [list]
        for {set i 1} {$i <= $k} {incr i} {
    	   lappend cL $c($i)
        }
        return $cL
    }
    
    
    #
    # nextKsubset
    # Returns next k-subset given a current k-subset.
    # Translates to ordinal numbers, calls nextK and translates back.
    #
    proc nextKsubset {setListName k {subsetList {}}} {
        upvar $setListName nList
        set ordinalList [list]
        foreach elem $subsetList {
    	   if {[set ndx [lsearch $nList $elem]] == -1} {
    	       error "element in subsetList not in setList: $elem"
    	   }
    	   lappend ordinalList [expr $ndx + 1]
        }
        set nextList [nextK [llength $nList] $k $ordinalList]
        set kList [list]
        foreach ndx $nextList {
    	   lappend kList [lindex $nList [expr $ndx - 1]]
        }
        return $kList
    }
        
    # set alphabet [list a b c d e f g h i j k l m n o p q r s t u v w x y z]
    # set count 0
    # set thisK {}
    # while {[llength [set thisK [nextKsubset alphabet 23 $thisK]]]} {
    #     incr count
    #     puts [join $thisK ""]
    # }
    # puts "count=$count"
    # package require math
    # puts [::math::choose [llength $alfabet] 23]

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