basis/math/combinatorics/combinatorics-docs.factor

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