basis/math/combinatorics/combinatorics-docs.factor

   1 USING: help.markup help.syntax kernel math math.order sequences ;
   2 IN: math.combinatorics
   3
   4 HELP: factorial
   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" } "." }
   7 { $examples
   8     { $example "USING: math.combinatorics prettyprint ;"
   9         "4 factorial ." "24" }
  10 } ;
  11
  12 HELP: nPk
  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" } "." }
  15 { $examples
  16     { $example "USING: math.combinatorics prettyprint ;"
  17         "10 4 nPk ." "5040" }
  18 } ;
  19
  20 HELP: nCk
  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\"." }
  23 { $examples
  24     { $example "USING: math.combinatorics prettyprint ;"
  25         "10 4 nCk ." "210" }
  26 } ;
  27
  28 HELP: permutation
  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 -" } "." }
  32 { $examples
  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\" }" }
  37 } ;
  38
  39 HELP: <permutations>
  40 { $values { "seq" sequence } { "permutations" sequence } }
  41 { $description "An efficient sequence containing the lexicographical permutations of " { $snippet "seq" } "." } ;
  42
  43 HELP: all-permutations
  44 { $values { "seq" sequence } { "seq'" sequence } }
  45 { $description "Outputs a sequence containing all permutations of " { $snippet "seq" } " in lexicographical order." }
  46 { $examples
  47     { $example "USING: math.combinatorics prettyprint ;"
  48         "{ 0 1 2 } all-permutations ." "{ { 0 1 2 } { 0 2 1 } { 1 0 2 } { 1 2 0 } { 2 0 1 } { 2 1 0 } }" }
  49 } ;
  50
  51 HELP: each-permutation
  52 { $values { "seq" sequence } { "quot" { $quotation "( ... elt -- ... )" } } }
  53 { $description "Applies the quotation to each permutation of " { $snippet "seq" } " in order." } ;
  54
  55 HELP: inverse-permutation
  56 { $values { "seq" sequence } { "permutation" sequence } }
  57 { $description "Outputs a sequence of indices representing the lexicographical permutation of " { $snippet "seq" } "." }
  58 { $notes "All items in " { $snippet "seq" } " must be comparable by " { $link <=> } "." }
  59 { $examples
  60     { $example "USING: math.combinatorics prettyprint ;"
  61         "\"dcba\" inverse-permutation ." "{ 3 2 1 0 }" }
  62     { $example "USING: math.combinatorics prettyprint ;"
  63         "{ 12 56 34 78 } inverse-permutation ." "{ 0 2 1 3 }" }
  64 } ;
  65
  66 HELP: combination
  67 { $values { "m" "a non-negative integer" } { "seq" sequence } { "k" "a non-negative integer" } { "seq'" sequence } }
  68 { $description "Outputs the " { $snippet "mth" } " lexicographical combination of " { $snippet "seq" } " choosing " { $snippet "k" } " elements." }
  69 { $notes "Combinations are 0-based and a bounds error will be thrown if " { $snippet "m" } " is larger than " { $snippet "seq length k nCk" } "." }
  70 { $examples
  71     { $example "USING: math.combinatorics sequences prettyprint ;"
  72         "6 7 iota 4 combination ." "{ 0 1 3 6 }" }
  73     { $example "USING: math.combinatorics prettyprint ;"
  74         "0 { \"a\" \"b\" \"c\" \"d\" } 2 combination ." "{ \"a\" \"b\" }" }
  75 } ;
  76
  77 HELP: <combinations>
  78 { $values { "seq" sequence } { "k" "a non-negative integer" } { "combinations" sequence } }
  79 { $description "An efficient sequence containing the combinations of " { $snippet "seq" } " choosing " { $snippet "k" } " elements." } ;
  80
  81 HELP: all-combinations
  82 { $values { "seq" sequence } { "k" "a non-negative integer" } { "seq'" sequence } }
  83 { $description "Outputs a sequence containing all combinations of " { $snippet "seq" } " choosing " { $snippet "k" } " elements, in lexicographical order." }
  84 { $examples
  85     { $example "USING: math.combinatorics prettyprint ;"
  86         "{ \"a\" \"b\" \"c\" \"d\" } 2 all-combinations ."
  87 """{
  88     { "a" "b" }
  89     { "a" "c" }
  90     { "a" "d" }
  91     { "b" "c" }
  92     { "b" "d" }
  93     { "c" "d" }
  94 }""" } } ;
  95
  96 HELP: each-combination
  97 { $values { "seq" sequence } { "k" "a non-negative integer" } { "quot" { $quotation "( ... elt -- ... )" } } }
  98 { $description "Applies the quotation to each combination of " { $snippet "seq" } " choosing " { $snippet "k" } " elements, in order." } ;
  99
 100
 101 IN: math.combinatorics.private
 102
 103 HELP: factoradic
 104 { $values { "n" integer } { "factoradic" sequence } }
 105 { $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." }
 106 { $examples { $example "USING: math.combinatorics.private  prettyprint ;" "859 factoradic ." "{ 1 1 0 3 0 1 0 }" } } ;
 107
 108 HELP: >permutation
 109 { $values { "factoradic" sequence } { "permutation" sequence } }
 110 { $description "Converts an integer represented in factoradic form into its corresponding unique permutation (0-based)." }
 111 { $notes "For clarification, the following two statements are equivalent:" { $code "10 factoradic >permutation" "{ 1 2 0 0 } >permutation" } }
 112 { $examples { $example "USING: math.combinatorics.private prettyprint ;" "{ 0 0 0 0 } >permutation ." "{ 0 1 2 3 }" } } ;
 113
 114 HELP: next-permutation
 115 { $values { "seq" sequence } }
 116 { $description "Rearranges the elements in " { $snippet "seq" } " into the lexicographically next greater permutation of elements." }
 117 { $notes "Performs an in-place modification of " { $snippet "seq" } "." }
 118 { $examples { $example "USING: math.combinatorics prettyprint ;" "\"ABC\" next-permutation ." "\"ACB\"" } } ;
 119
 120 HELP: all-subsets
 121 { $values { "seq" sequence } { "subsets" sequence } }
 122 { $description
 123     "Returns all the subsets of a sequence."
 124 }
 125 { $examples
 126     { $example
 127         "USING: math.combinatorics prettyprint ;"
 128         "{ 1 2 3 } all-subsets ."
 129         "{ { } { 1 } { 2 } { 3 } { 1 2 } { 1 3 } { 2 3 } { 1 2 3 } }"
 130     }
 131 } ;
 132
 133 HELP: selections
 134 { $values { "seq" sequence } { "n" integer } { "selections" sequence } }
 135 { $description
 136     "Returns all the ways to take n (possibly the same) items from the "
 137     "sequence of items."
 138 }
 139 { $examples
 140     { $example
 141         "USING: math.combinatorics prettyprint ;"
 142         "{ 1 2 } 2 selections ."
 143         "{ { 1 1 } { 1 2 } { 2 1 } { 2 2 } }"
 144     }
 145 } ;