Note: Content on this page is very similar to Permutations. buchs
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]Daniel B: Here's the reverse if anyone needs it, albeit done without great concern for efficency and rather ugly, but it suited my needs Given pairs, or other sets, give me all the combinations that use one entry from each set. Lars H: That description sounds awfully much like the cartesian product of a list of lists.
# CombineSets --
#
# Generates a list of possible combinations when given a list of paired values
# or any other set of sets (triples, quads, etc.)
# so... {4 5} {8 10} would return {4 8} {4 10} {5 8} {5 10}
proc CombineSets {sets} {
# Are we dealing with pairs, triples, or what
set example_entry [lindex $sets 0]
set set_length [llength [split $example_entry]]
set number_of_sets [llength $sets]
set number_of_entries [expr $number_of_sets * $set_length]
set number_list start
set entry_length 0
while {$entry_length < $number_of_sets} {
set number_list [NextSets $set_length $sets $number_list]
# Get the length of one of the returned entries...
set entry_length [llength [lindex $number_list 0]]
}
set number_list [lsort -dictionary -unique $number_list]
puts "\nAll [llength $number_list] combinations of sets: $sets\nare:\n $number_list"
return $number_list
}
# NextSets --
#
# Returns the next set - used with CombineSets
proc NextSets {set_length all_sets number_list} {
set new_number_list ""
foreach l $number_list {
if {$l == "start"} {
set current_length 0
set l ""
} else {
set current_length [llength $l]
}
set current_set [lindex $all_sets $current_length]
for {set c [expr $set_length - 1]} {$c >= 0} {incr c -1} {
if {$l != ""} {
lappend new_number_list [linsert $l end [lindex $current_set $c]]
} else {
lappend new_number_list [lindex $current_set $c]
}
}
}
return $new_number_list
}
(bin) 214 % CombineSets [list {1 2} {3 4} {5 6}]
All 8 combinations of sets: {1 2} {3 4} {5 6}
are:
{1 3 5} {1 3 6} {1 4 5} {1 4 6} {2 3 5} {2 3 6} {2 4 5} {2 4 6}Problem: I want to have all combinations of capitalization of the letters of a word.
The solution is posted as part of a larger problem solution, generating all possible combinations of all possible capitalizations of six words chosen from a list of N words. See CombinationCapitalization
See also