1 USING: help.markup help.syntax kernel math math.order sequences ;
5 { $values { "n" "a non-negative integer" } { "n!" integer } }
6 { $description "Outputs the product of all positive integers less than or equal to " { $snippet "n" } "." }
8 { $example "USING: math.combinatorics prettyprint ;"
13 { $values { "n" "a non-negative integer" } { "k" "a non-negative integer" } { "nPk" integer } }
14 { $description "Outputs the total number of unique permutations of size " { $snippet "k" } " (order does matter) that can be taken from a set of size " { $snippet "n" } "." }
16 { $example "USING: math.combinatorics prettyprint ;"
21 { $values { "n" "a non-negative integer" } { "k" "a non-negative integer" } { "nCk" integer } }
22 { $description "Outputs the total number of unique combinations of size " { $snippet "k" } " (order does not matter) that can be taken from a set of size " { $snippet "n" } ". Commonly written as \"n choose k\"." }
24 { $example "USING: math.combinatorics prettyprint ;"
29 { $values { "n" "a non-negative integer" } { "seq" sequence } { "seq'" sequence } }
30 { $description "Outputs the " { $snippet "nth" } " lexicographical permutation of " { $snippet "seq" } "." }
31 { $notes "Permutations are 0-based and a bounds error will be thrown if " { $snippet "n" } " is larger than " { $snippet "seq length factorial 1 -" } "." }
33 { $example "USING: math.combinatorics prettyprint ;"
34 "1 { 0 1 2 } permutation ." "{ 0 2 1 }" }
35 { $example "USING: math.combinatorics prettyprint ;"
36 "5 { \"apple\" \"banana\" \"orange\" } permutation ." "{ \"orange\" \"banana\" \"apple\" }" }
40 { $values { "seq" sequence } { "permutations" sequence } }
41 { $description "An efficient sequence containing the lexicographical permutations of " { $snippet "seq" } "." } ;
43 HELP: <k-permutations>
44 { $values { "seq" sequence } { "k" integer } { "permutations" sequence } }
45 { $description "An efficient sequence containing the " { $snippet "k" } " lexicographical permutations of " { $snippet "seq" } "." } ;
47 HELP: all-permutations
48 { $values { "seq" sequence } { "seq'" sequence } }
49 { $description "Outputs a sequence containing all permutations of " { $snippet "seq" } " in lexicographical order." }
51 { $example "USING: math.combinatorics prettyprint ;"
52 "{ 0 1 2 } all-permutations ." "{ { 0 1 2 } { 0 2 1 } { 1 0 2 } { 1 2 0 } { 2 0 1 } { 2 1 0 } }" }
55 HELP: each-permutation
56 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... ) } } }
57 { $description "Applies the quotation to each permutation of " { $snippet "seq" } " in order." } ;
59 HELP: inverse-permutation
60 { $values { "seq" sequence } { "permutation" sequence } }
61 { $description "Outputs a sequence of indices representing the lexicographical permutation of " { $snippet "seq" } "." }
62 { $notes "All items in " { $snippet "seq" } " must be comparable by " { $link <=> } "." }
64 { $example "USING: math.combinatorics prettyprint ;"
65 "\"dcba\" inverse-permutation ." "{ 3 2 1 0 }" }
66 { $example "USING: math.combinatorics prettyprint ;"
67 "{ 12 56 34 78 } inverse-permutation ." "{ 0 2 1 3 }" }
71 { $values { "m" "a non-negative integer" } { "seq" sequence } { "k" "a non-negative integer" } { "seq'" sequence } }
72 { $description "Outputs the " { $snippet "mth" } " lexicographical combination of " { $snippet "seq" } " choosing " { $snippet "k" } " elements." }
73 { $notes "Combinations are 0-based and a bounds error will be thrown if " { $snippet "m" } " is larger than " { $snippet "seq length k nCk" } "." }
75 { $example "USING: math.combinatorics sequences prettyprint ;"
76 "6 7 iota 4 combination ." "{ 0 1 3 6 }" }
77 { $example "USING: math.combinatorics prettyprint ;"
78 "0 { \"a\" \"b\" \"c\" \"d\" } 2 combination ." "{ \"a\" \"b\" }" }
82 { $values { "seq" sequence } { "k" "a non-negative integer" } { "combinations" sequence } }
83 { $description "An efficient sequence containing the combinations of " { $snippet "seq" } " choosing " { $snippet "k" } " elements." } ;
85 HELP: all-combinations
86 { $values { "seq" sequence } { "k" "a non-negative integer" } { "seq'" sequence } }
87 { $description "Outputs a sequence containing all combinations of " { $snippet "seq" } " choosing " { $snippet "k" } " elements, in lexicographical order." }
89 { $example "USING: math.combinatorics prettyprint ;"
90 "{ \"a\" \"b\" \"c\" \"d\" } 2 all-combinations ."
100 HELP: each-combination
101 { $values { "seq" sequence } { "k" "a non-negative integer" } { "quot" { $quotation ( ... elt -- ... ) } } }
102 { $description "Applies the quotation to each combination of " { $snippet "seq" } " choosing " { $snippet "k" } " elements, in order." } ;
107 { $values { "n" integer } { "factoradic" sequence } }
108 { $description "Converts a positive integer " { $snippet "n" } " to factoradic form. The factoradic of an integer is its representation based on a mixed radix numerical system that corresponds to the values of " { $snippet "n" } " factorial." }
109 { $examples { $example "USING: math.combinatorics.private prettyprint ;" "859 factoradic ." "{ 1 1 0 3 0 1 0 }" } } ;
112 { $values { "factoradic" sequence } { "permutation" sequence } }
113 { $description "Converts an integer represented in factoradic form into its corresponding unique permutation (0-based)." }
114 { $notes "For clarification, the following two statements are equivalent:" { $code "10 factoradic >permutation" "{ 1 2 0 0 } >permutation" } }
115 { $examples { $example "USING: math.combinatorics.private prettyprint ;" "{ 0 0 0 0 } >permutation ." "{ 0 1 2 3 }" } } ;
117 HELP: next-permutation
118 { $values { "seq" sequence } }
119 { $description "Rearranges the elements in " { $snippet "seq" } " into the lexicographically next greater permutation of elements." }
120 { $notes "Performs an in-place modification of " { $snippet "seq" } "." }
121 { $examples { $example "USING: math.combinatorics prettyprint ;" "\"ABC\" next-permutation ." "\"ACB\"" } } ;
124 { $values { "seq" sequence } { "subsets" sequence } }
126 "Returns all the subsets of a sequence."
130 "USING: math.combinatorics prettyprint ;"
131 "{ 1 2 3 } all-subsets ."
132 "{ { } { 1 } { 2 } { 3 } { 1 2 } { 1 3 } { 2 3 } { 1 2 3 } }"
137 { $values { "seq" sequence } { "n" integer } { "selections" sequence } }
139 "Returns all the ways to take n (possibly the same) items from the "
144 "USING: math.combinatorics prettyprint ;"
145 "{ 1 2 } 2 selections ."
146 "{ { 1 1 } { 1 2 } { 2 1 } { 2 2 } }"