Move math.combinatorics to basis

diff --git a/basis/math/combinatorics/authors.txt b/basis/math/combinatorics/authors.txt
new file mode 100644 (file)
index 0000000..708cc3e
--- /dev/null
+++ b/basis/math/combinatorics/authors.txt
@@ -0,0 +1,3 @@
+Slava Pestov
+Doug Coleman
+Aaron Schaefer

diff --git a/basis/math/combinatorics/combinatorics-docs.factor b/basis/math/combinatorics/combinatorics-docs.factor
new file mode 100644 (file)
index 0000000..514c808
--- /dev/null
+++ b/basis/math/combinatorics/combinatorics-docs.factor
@@ -0,0 +1,49 @@
+USING: help.markup help.syntax kernel math math.order sequences ;
+IN: math.combinatorics
+
+HELP: factorial
+{ $values { "n" "a non-negative integer" } { "n!" integer } }
+{ $description "Outputs the product of all positive integers less than or equal to " { $snippet "n" } "." }
+{ $examples { $example "USING: math.combinatorics prettyprint ;" "4 factorial ." "24" } } ;
+
+HELP: nPk
+{ $values { "n" "a non-negative integer" } { "k" "a non-negative integer" } { "nPk" integer } }
+{ $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" } "." }
+{ $examples { $example "USING: math.combinatorics prettyprint ;" "10 4 nPk ." "5040" } } ;
+
+HELP: nCk
+{ $values { "n" "a non-negative integer" } { "k" "a non-negative integer" } { "nCk" integer } }
+{ $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\"." }
+{ $examples { $example "USING: math.combinatorics prettyprint ;" "10 4 nCk ." "210" } } ;
+
+HELP: permutation
+{ $values { "n" "a non-negative integer" } { "seq" sequence } { "seq" sequence } }
+{ $description "Outputs the " { $snippet "nth" } " lexicographical permutation of " { $snippet "seq" } "." }
+{ $notes "Permutations are 0-based and a bounds error will be thrown if " { $snippet "n" } " is larger than " { $snippet "seq length factorial 1-" } "." }
+{ $examples { $example "USING: math.combinatorics prettyprint ;" "1 3 permutation ." "{ 0 2 1 }" } { $example "USING: math.combinatorics prettyprint ;" "5 { \"apple\" \"banana\" \"orange\" } permutation ." "{ \"orange\" \"banana\" \"apple\" }" } } ;
+
+HELP: all-permutations
+{ $values { "seq" sequence } { "seq" sequence } }
+{ $description "Outputs a sequence containing all permutations of " { $snippet "seq" } " in lexicographical order." }
+{ $examples { $example "USING: math.combinatorics prettyprint ;" "3 all-permutations ." "{ { 0 1 2 } { 0 2 1 } { 1 0 2 } { 1 2 0 } { 2 0 1 } { 2 1 0 } }" } } ;
+
+HELP: inverse-permutation
+{ $values { "seq" sequence } { "permutation" sequence } }
+{ $description "Outputs a sequence of indices representing the lexicographical permutation of " { $snippet "seq" } "." }
+{ $notes "All items in " { $snippet "seq" } " must be comparable by " { $link <=> } "." }
+{ $examples { $example "USING: math.combinatorics prettyprint ;" "\"dcba\" inverse-permutation ." "{ 3 2 1 0 }" } { $example "USING: math.combinatorics prettyprint ;" "{ 12 56 34 78 } inverse-permutation ." "{ 0 2 1 3 }" } } ;
+
+
+IN: math.combinatorics.private
+
+HELP: factoradic
+{ $values { "n" integer } { "factoradic" sequence } }
+{ $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." }
+{ $examples { $example "USING: math.combinatorics.private  prettyprint ;" "859 factoradic ." "{ 1 1 0 3 0 1 0 }" } } ;
+
+HELP: >permutation
+{ $values { "factoradic" sequence } { "permutation" sequence } }
+{ $description "Converts an integer represented in factoradic form into its corresponding unique permutation (0-based)." }
+{ $notes "For clarification, the following two statements are equivalent:" { $code "10 factoradic >permutation" "{ 1 2 0 0 } >permutation" } }
+{ $examples { $example "USING: math.combinatorics.private prettyprint ;" "{ 0 0 0 0 } >permutation ." "{ 0 1 2 3 }" } } ;
+

diff --git a/basis/math/combinatorics/combinatorics-tests.factor b/basis/math/combinatorics/combinatorics-tests.factor
new file mode 100644 (file)
index 0000000..5ef435a
--- /dev/null
+++ b/basis/math/combinatorics/combinatorics-tests.factor
@@ -0,0 +1,45 @@
+USING: math.combinatorics math.combinatorics.private tools.test ;
+IN: math.combinatorics.tests
+
+[ { } ] [ 0 factoradic ] unit-test
+[ { 1 0 } ] [ 1 factoradic ] unit-test
+[ { 1 1 0 3 0 1 0 } ] [ 859 factoradic ] unit-test
+
+[ { 0 1 2 3 } ] [ { 0 0 0 0 } >permutation ] unit-test
+[ { 0 1 3 2 } ] [ { 0 0 1 0 } >permutation ] unit-test
+[ { 1 2 0 6 3 5 4 } ] [ { 1 1 0 3 0 1 0 } >permutation ] unit-test
+
+[ { 0 1 2 3 } ] [ 0 4 permutation-indices ] unit-test
+[ { 0 1 3 2 } ] [ 1 4 permutation-indices ] unit-test
+[ { 1 2 0 6 3 5 4 } ] [ 859 7 permutation-indices ] unit-test
+
+[ 1 ] [ 0 factorial ] unit-test
+[ 1 ] [ 1 factorial ] unit-test
+[ 3628800 ] [ 10 factorial ] unit-test
+
+[ 1 ] [ 3 0 nPk ] unit-test
+[ 6 ] [ 3 2 nPk ] unit-test
+[ 6 ] [ 3 3 nPk ] unit-test
+[ 0 ] [ 3 4 nPk ] unit-test
+[ 311875200 ] [ 52 5 nPk ] unit-test
+[ 672151459757865654763838640470031391460745878674027315200000000000 ] [ 52 47 nPk ] unit-test
+
+[ 1 ] [ 3 0 nCk ] unit-test
+[ 3 ] [ 3 2 nCk ] unit-test
+[ 1 ] [ 3 3 nCk ] unit-test
+[ 0 ] [ 3 4 nCk ] unit-test
+[ 2598960 ] [ 52 5 nCk ] unit-test
+[ 2598960 ] [ 52 47 nCk ] unit-test
+
+[ { "a" "b" "c" "d" } ] [ 0 { "a" "b" "c" "d" } permutation ] unit-test
+[ { "d" "c" "b" "a" } ] [ 23 { "a" "b" "c" "d" } permutation ] unit-test
+[ { "d" "a" "b" "c" } ] [ 18 { "a" "b" "c" "d" } permutation ] unit-test
+
+[ { { "a" "b" "c" } { "a" "c" "b" }
+    { "b" "a" "c" } { "b" "c" "a" }
+    { "c" "a" "b" } { "c" "b" "a" } } ] [ { "a" "b" "c" } all-permutations ] unit-test
+
+[ { 0 1 2 } ] [ { "a" "b" "c" } inverse-permutation ] unit-test
+[ { 2 1 0 } ] [ { "c" "b" "a" } inverse-permutation ] unit-test
+[ { 3 0 2 1 } ] [ { 12 45 34 2 } inverse-permutation ] unit-test
+

diff --git a/basis/math/combinatorics/combinatorics.factor b/basis/math/combinatorics/combinatorics.factor
new file mode 100644 (file)
index 0000000..1bc692c
--- /dev/null
+++ b/basis/math/combinatorics/combinatorics.factor
@@ -0,0 +1,55 @@
+! Copyright (c) 2007, 2008 Slava Pestov, Doug Coleman, Aaron Schaefer.
+! See http://factorcode.org/license.txt for BSD license.
+USING: assocs kernel math math.order math.ranges mirrors
+namespaces sequences sorting fry ;
+IN: math.combinatorics
+
+<PRIVATE
+
+: possible? ( n m -- ? )
+    0 rot between? ; inline
+
+: twiddle ( n k -- n k )
+    2dup - dupd > [ dupd - ] when ; inline
+
+! See this article for explanation of the factoradic-based permutation methodology:
+! http://msdn2.microsoft.com/en-us/library/aa302371.aspx
+
+: factoradic ( n -- factoradic )
+    0 [ over 0 > ] [ 1+ [ /mod ] keep swap ] [ ] produce reverse 2nip ;
+
+: (>permutation) ( seq n -- seq )
+    [ '[ _ dupd >= [ 1+ ] when ] map ] keep prefix ;
+
+: >permutation ( factoradic -- permutation )
+    reverse 1 cut [ (>permutation) ] each ;
+
+: permutation-indices ( n seq -- permutation )
+    length [ factoradic ] dip 0 pad-left >permutation ;
+
+PRIVATE>
+
+: factorial ( n -- n! )
+    1 [ 1+ * ] reduce ;
+
+: nPk ( n k -- nPk )
+    2dup possible? [ dupd - [a,b) product ] [ 2drop 0 ] if ;
+
+: nCk ( n k -- nCk )
+    twiddle [ nPk ] keep factorial / ;
+
+: permutation ( n seq -- seq )
+    [ permutation-indices ] keep nths ;
+
+: all-permutations ( seq -- seq )
+    [ length factorial ] keep '[ _ permutation ] map ;
+
+: each-permutation ( seq quot -- )
+    [ [ length factorial ] keep ] dip
+    '[ _ permutation @ ] each ; inline
+
+: reduce-permutations ( seq initial quot -- result )
+    swapd each-permutation ; inline
+
+: inverse-permutation ( seq -- permutation )
+    <enum> >alist sort-values keys ;

diff --git a/basis/math/combinatorics/summary.txt b/basis/math/combinatorics/summary.txt
new file mode 100644 (file)
index 0000000..ecd43de
--- /dev/null
+++ b/basis/math/combinatorics/summary.txt
@@ -0,0 +1 @@
+Permutations and combinations

diff --git a/extra/math/combinatorics/authors.txt b/extra/math/combinatorics/authors.txt
deleted file mode 100644 (file)
index 708cc3e..0000000
--- a/extra/math/combinatorics/authors.txt
+++ /dev/null
@@ -1,3 +0,0 @@
-Slava Pestov
-Doug Coleman
-Aaron Schaefer

diff --git a/extra/math/combinatorics/combinatorics-docs.factor b/extra/math/combinatorics/combinatorics-docs.factor
deleted file mode 100644 (file)
index 514c808..0000000
--- a/extra/math/combinatorics/combinatorics-docs.factor
+++ /dev/null
@@ -1,49 +0,0 @@
-USING: help.markup help.syntax kernel math math.order sequences ;
-IN: math.combinatorics
-
-HELP: factorial
-{ $values { "n" "a non-negative integer" } { "n!" integer } }
-{ $description "Outputs the product of all positive integers less than or equal to " { $snippet "n" } "." }
-{ $examples { $example "USING: math.combinatorics prettyprint ;" "4 factorial ." "24" } } ;
-
-HELP: nPk
-{ $values { "n" "a non-negative integer" } { "k" "a non-negative integer" } { "nPk" integer } }
-{ $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" } "." }
-{ $examples { $example "USING: math.combinatorics prettyprint ;" "10 4 nPk ." "5040" } } ;
-
-HELP: nCk
-{ $values { "n" "a non-negative integer" } { "k" "a non-negative integer" } { "nCk" integer } }
-{ $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\"." }
-{ $examples { $example "USING: math.combinatorics prettyprint ;" "10 4 nCk ." "210" } } ;
-
-HELP: permutation
-{ $values { "n" "a non-negative integer" } { "seq" sequence } { "seq" sequence } }
-{ $description "Outputs the " { $snippet "nth" } " lexicographical permutation of " { $snippet "seq" } "." }
-{ $notes "Permutations are 0-based and a bounds error will be thrown if " { $snippet "n" } " is larger than " { $snippet "seq length factorial 1-" } "." }
-{ $examples { $example "USING: math.combinatorics prettyprint ;" "1 3 permutation ." "{ 0 2 1 }" } { $example "USING: math.combinatorics prettyprint ;" "5 { \"apple\" \"banana\" \"orange\" } permutation ." "{ \"orange\" \"banana\" \"apple\" }" } } ;
-
-HELP: all-permutations
-{ $values { "seq" sequence } { "seq" sequence } }
-{ $description "Outputs a sequence containing all permutations of " { $snippet "seq" } " in lexicographical order." }
-{ $examples { $example "USING: math.combinatorics prettyprint ;" "3 all-permutations ." "{ { 0 1 2 } { 0 2 1 } { 1 0 2 } { 1 2 0 } { 2 0 1 } { 2 1 0 } }" } } ;
-
-HELP: inverse-permutation
-{ $values { "seq" sequence } { "permutation" sequence } }
-{ $description "Outputs a sequence of indices representing the lexicographical permutation of " { $snippet "seq" } "." }
-{ $notes "All items in " { $snippet "seq" } " must be comparable by " { $link <=> } "." }
-{ $examples { $example "USING: math.combinatorics prettyprint ;" "\"dcba\" inverse-permutation ." "{ 3 2 1 0 }" } { $example "USING: math.combinatorics prettyprint ;" "{ 12 56 34 78 } inverse-permutation ." "{ 0 2 1 3 }" } } ;
-
-
-IN: math.combinatorics.private
-
-HELP: factoradic
-{ $values { "n" integer } { "factoradic" sequence } }
-{ $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." }
-{ $examples { $example "USING: math.combinatorics.private  prettyprint ;" "859 factoradic ." "{ 1 1 0 3 0 1 0 }" } } ;
-
-HELP: >permutation
-{ $values { "factoradic" sequence } { "permutation" sequence } }
-{ $description "Converts an integer represented in factoradic form into its corresponding unique permutation (0-based)." }
-{ $notes "For clarification, the following two statements are equivalent:" { $code "10 factoradic >permutation" "{ 1 2 0 0 } >permutation" } }
-{ $examples { $example "USING: math.combinatorics.private prettyprint ;" "{ 0 0 0 0 } >permutation ." "{ 0 1 2 3 }" } } ;
-

diff --git a/extra/math/combinatorics/combinatorics-tests.factor b/extra/math/combinatorics/combinatorics-tests.factor
deleted file mode 100644 (file)
index 5ef435a..0000000
--- a/extra/math/combinatorics/combinatorics-tests.factor
+++ /dev/null
@@ -1,45 +0,0 @@
-USING: math.combinatorics math.combinatorics.private tools.test ;
-IN: math.combinatorics.tests
-
-[ { } ] [ 0 factoradic ] unit-test
-[ { 1 0 } ] [ 1 factoradic ] unit-test
-[ { 1 1 0 3 0 1 0 } ] [ 859 factoradic ] unit-test
-
-[ { 0 1 2 3 } ] [ { 0 0 0 0 } >permutation ] unit-test
-[ { 0 1 3 2 } ] [ { 0 0 1 0 } >permutation ] unit-test
-[ { 1 2 0 6 3 5 4 } ] [ { 1 1 0 3 0 1 0 } >permutation ] unit-test
-
-[ { 0 1 2 3 } ] [ 0 4 permutation-indices ] unit-test
-[ { 0 1 3 2 } ] [ 1 4 permutation-indices ] unit-test
-[ { 1 2 0 6 3 5 4 } ] [ 859 7 permutation-indices ] unit-test
-
-[ 1 ] [ 0 factorial ] unit-test
-[ 1 ] [ 1 factorial ] unit-test
-[ 3628800 ] [ 10 factorial ] unit-test
-
-[ 1 ] [ 3 0 nPk ] unit-test
-[ 6 ] [ 3 2 nPk ] unit-test
-[ 6 ] [ 3 3 nPk ] unit-test
-[ 0 ] [ 3 4 nPk ] unit-test
-[ 311875200 ] [ 52 5 nPk ] unit-test
-[ 672151459757865654763838640470031391460745878674027315200000000000 ] [ 52 47 nPk ] unit-test
-
-[ 1 ] [ 3 0 nCk ] unit-test
-[ 3 ] [ 3 2 nCk ] unit-test
-[ 1 ] [ 3 3 nCk ] unit-test
-[ 0 ] [ 3 4 nCk ] unit-test
-[ 2598960 ] [ 52 5 nCk ] unit-test
-[ 2598960 ] [ 52 47 nCk ] unit-test
-
-[ { "a" "b" "c" "d" } ] [ 0 { "a" "b" "c" "d" } permutation ] unit-test
-[ { "d" "c" "b" "a" } ] [ 23 { "a" "b" "c" "d" } permutation ] unit-test
-[ { "d" "a" "b" "c" } ] [ 18 { "a" "b" "c" "d" } permutation ] unit-test
-
-[ { { "a" "b" "c" } { "a" "c" "b" }
-    { "b" "a" "c" } { "b" "c" "a" }
-    { "c" "a" "b" } { "c" "b" "a" } } ] [ { "a" "b" "c" } all-permutations ] unit-test
-
-[ { 0 1 2 } ] [ { "a" "b" "c" } inverse-permutation ] unit-test
-[ { 2 1 0 } ] [ { "c" "b" "a" } inverse-permutation ] unit-test
-[ { 3 0 2 1 } ] [ { 12 45 34 2 } inverse-permutation ] unit-test
-

diff --git a/extra/math/combinatorics/combinatorics.factor b/extra/math/combinatorics/combinatorics.factor
deleted file mode 100644 (file)
index 1bc692c..0000000
--- a/extra/math/combinatorics/combinatorics.factor
+++ /dev/null
@@ -1,55 +0,0 @@
-! Copyright (c) 2007, 2008 Slava Pestov, Doug Coleman, Aaron Schaefer.
-! See http://factorcode.org/license.txt for BSD license.
-USING: assocs kernel math math.order math.ranges mirrors
-namespaces sequences sorting fry ;
-IN: math.combinatorics
-
-<PRIVATE
-
-: possible? ( n m -- ? )
-    0 rot between? ; inline
-
-: twiddle ( n k -- n k )
-    2dup - dupd > [ dupd - ] when ; inline
-
-! See this article for explanation of the factoradic-based permutation methodology:
-! http://msdn2.microsoft.com/en-us/library/aa302371.aspx
-
-: factoradic ( n -- factoradic )
-    0 [ over 0 > ] [ 1+ [ /mod ] keep swap ] [ ] produce reverse 2nip ;
-
-: (>permutation) ( seq n -- seq )
-    [ '[ _ dupd >= [ 1+ ] when ] map ] keep prefix ;
-
-: >permutation ( factoradic -- permutation )
-    reverse 1 cut [ (>permutation) ] each ;
-
-: permutation-indices ( n seq -- permutation )
-    length [ factoradic ] dip 0 pad-left >permutation ;
-
-PRIVATE>
-
-: factorial ( n -- n! )
-    1 [ 1+ * ] reduce ;
-
-: nPk ( n k -- nPk )
-    2dup possible? [ dupd - [a,b) product ] [ 2drop 0 ] if ;
-
-: nCk ( n k -- nCk )
-    twiddle [ nPk ] keep factorial / ;
-
-: permutation ( n seq -- seq )
-    [ permutation-indices ] keep nths ;
-
-: all-permutations ( seq -- seq )
-    [ length factorial ] keep '[ _ permutation ] map ;
-
-: each-permutation ( seq quot -- )
-    [ [ length factorial ] keep ] dip
-    '[ _ permutation @ ] each ; inline
-
-: reduce-permutations ( seq initial quot -- result )
-    swapd each-permutation ; inline
-
-: inverse-permutation ( seq -- permutation )
-    <enum> >alist sort-values keys ;

diff --git a/extra/math/combinatorics/summary.txt b/extra/math/combinatorics/summary.txt
deleted file mode 100644 (file)
index ecd43de..0000000
--- a/extra/math/combinatorics/summary.txt
+++ /dev/null
@@ -1 +0,0 @@
-Permutations and combinations