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