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 alfabet [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 alfabet 23 $thisK]]]} {
# incr count
# puts [join $thisK ""]
# }
# puts "count=$count"
# package require math
# puts [::math::choose [llength $alfabet] 23]See also