SUBSET
Combinatorial Routines
SUBSET
is a FORTRAN77 library which
enumerates, generates, randomizes, ranks and unranks combinatorial objects
including combinations, compositions, Gray codes, index sets, partitions,
permutations, polynomials, subsets, and Young tables. Backtracking
routines are included to solve some combinatorial problems.
These include the enumeration, generation, random
selection, ranking and unranking of
-
COMP, compositions of an integer N into K parts;
-
COMPNZ, compositions of an integer N into K parts,
with no zero parts;
-
EQUIV's, partitions of a set of N objects;
-
I4_PARTITION's, partitions of an integer;
-
I4POLY's, integer polynomials in factorial, Newton,
power sum, or Taylor form;
-
I4VEC's, integer vectors;
-
KSUB's, subsets of size K, from a set of N objects;
-
MULTIPERM's, permutations of the N objects, some of which
are indistinguishable.
-
PERM's, permutations of the first N integers;
-
R8POLY's, real polynomials in factorial, Newton,
power sum, or Taylor form;
-
KSUB's, subsets of a set of N objects;
-
vectors whose entries range from 1 to N;
-
YTB's, Young tables;
Other objects considered include
-
the Bell numbers,
-
BVEC's, binary numbers represented as a vector of 0's and 1's;
-
Catalan numbers,
-
congruence equations.
-
continued fractions,
-
DEC's, decimal numbers represented as a mantissa and a power of 10;
-
DERANGE's, derangements (permutations that leave no element in place),
-
DVEC's, decimal numbers represented as a vector of digits;
-
falling factorials (20*19*18...),
-
Gray codes,
-
matrix permanents (similar to determinants, but harder to compute,
if you can believe that),
-
Morse-Thue numbers,
-
pentagonal numbers,
-
Pythagorean triples,
-
RAT's, rational numbers represented as a pair of integers;
-
rising factorials (7*8*9...).
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Languages:
SUBSET is available in
a C version and
a C++ version and
a FORTRAN77 version and
a FORTRAN90 version and
a MATLAB version and
a Python version.
Related Data and Programs:
BACKTRACK_BINARY_RC,
a FORTRAN77 library which
carries out a backtrack search for a set of binary decisions, using
reverse communication.
CHANGE_MAKING,
a FORTRAN77 library which
considers the change making problem,
in which a given sum is to be formed using coins of various denominations.
COMBINATION_LOCK,
a FORTRAN77 program which
simulates the process of determining the secret combination of a lock.
COMBO,
a FORTRAN77 library which
contains a variety of combinatorial routines.
KNAPSACK_01,
a FORTRAN77 library which
uses brute force to solve small versions of the 0/1 knapsack problem;
LEGENDRE_PRODUCT_POLYNOMIAL,
a FORTRAN77 library which
defines Legendre product polynomials, creating a multivariate
polynomial as the product of univariate Legendre polynomials.
MONOMIAL,
a FORTRAN77 library which
enumerates, lists, ranks, unranks and randomizes multivariate monomials
in a space of M dimensions, with total degree less than N,
equal to N, or lying within a given range.
PARTITION_PROBLEM,
a FORTRAN77 library which
seeks solutions of the partition problem, splitting a set of integers into
two subsets with equal sum.
POLYNOMIAL,
a FORTRAN77 library which
adds, multiplies, differentiates, evaluates and prints multivariate
polynomials in a space of M dimensions.
Reference:
-
Milton Abramowitz, Irene Stegun,
Handbook of Mathematical Functions,
National Bureau of Standards, 1964,
ISBN: 0-486-61272-4,
LC: QA47.A34.
-
Walter Ball,
Mathematical Recreations and Essays,
Macmillan, 1962,
ISBN: 1417921269.
-
Paul Bratley, Bennett Fox, Linus Schrage,
A Guide to Simulation,
Second Edition,
Springer, 1987,
ISBN: 0387964673.
-
Bill Buckles, Matthew Lybanon,
Algorithm 515:
Generation of a Vector from the Lexicographical Index,
ACM Transactions on Mathematical Software,
Volume 3, Number 2, June 1977, pages 180-182.
-
Tom Christiansen, Nathan Torkington,
Perl Cookbook,
OReilly, 1999.
-
William Cody, Kenneth Hillstrom,
Chebyshev Approximations for the Natural Logarithm of the
Gamma Function,
Mathematics of Computation,
Volume 21, Number 98, April 1967, pages 198-203.
-
John Conway, Richard Guy,
The Book of Numbers,
Springer, 1998,
ISBN: 038797993X.
-
Bennett Fox,
Algorithm 647:
Implementation and Relative Efficiency of Quasirandom
Sequence Generators,
ACM Transactions on Mathematical Software,
Volume 12, Number 4, December 1986, pages 362-376.
-
Laurent Habsieger, Maxim Kazarian, Sergei Lando,
On the Second Number of Plutarch,
American Mathematical Monthly,
Volume 105, Number 5, May 1998, page 446.
-
John Halton,
On the efficiency of certain quasi-random sequences of points
in evaluating multi-dimensional integrals,
Numerische Mathematik,
Volume 2, Number 1, December 1960, pages 84-90.
-
John Hammersley,
Monte Carlo methods for solving multivariable problems,
Proceedings of the New York Academy of Science,
Volume 86, 1960, pages 844-874.
-
John Hart, Ward Cheney, Charles Lawson, Hans Maehly,
Charles Mesztenyi, John Rice, Henry Thatcher,
Christoph Witzgall,
Computer Approximations,
Wiley, 1968.
-
Brian Hayes,
Third Base,
American Scientist,
Volume 89, Number 6, November-December 2001, pages 490-494.
-
Mark Herkommer,
Number Theory, A Programmer's Guide,
McGraw Hill, 1999,
ISBN: 0-07-913074-7.
-
Karla Hoffman, Douglas Shier,
Algorithm 564:
A Test Problem Generator for Discrete Linear L1
Approximation Problems,
ACM Transactions on Mathematical Software,
Volume 6, Number 4, December 1980, pages 615-617.
-
Donald Knuth,
The Art of Computer Programming,
Volume 3, Sorting and Searching,
Second Edition,
Addison Wesley, 1998,
ISBN: 0201896850,
LC: QA76.6.K64.
-
Hang Tong Lau,
Algorithms on Graphs,
Tab Books, 1989,
ISBN: 0830634290
-
Pierre LEcuyer,
Random Number Generation,
in Handbook of Simulation,
edited by Jerry Banks,
Wiley, 1998,
ISBN: 0471134031,
LC: T57.62.H37.
-
Peter Lewis, Allen Goodman, James Miller,
A Pseudo-Random Number Generator for the System/360,
IBM Systems Journal,
Volume 8, 1969, pages 136-143.
-
Charles Mifsud,
Algorithm 154,
Combination in Lexicographic Order,
Communications of the ACM,
Volume 6, Number 3, March 1963, page 103.
-
mil_std_1753,
Military Standard 1753,
FORTRAN, DoD Supplement To American National Standard X3.9-1978,
9 November 1978.
-
Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0-12-519260-6,
LC: QA164.N54.
-
Robert Owens,
Sums of Powers of Integers,
Mathematics Magazine,
Volume 65, Number 1, February 1992, pages 38-40.
-
Norman Richert,
Strang's Strange Figures,
American Mathematical Monthly,
Volume 99, Number 2, February 1992, pages 101-107.
-
James Sandeson,
Testing Ecological Patterns,
American Scientist,
Volume 88, July-August 2000, pages 332-339.
-
Ian Saunders,
Algorithm AS 205,
Enumeration of R x C Tables with Repeated Row Totals,
Applied Statistics,
Volume 33, Number 3, 1984, pages 340-352.
-
Robert Sedgewick,
Algorithms in C,
Addison-Wesley, 1990,
ISBN: 0-201-51425-7,
LC: QA76.73.C15S43.
-
Raymond Seroul,
Programming for Mathematicians,
Springer, 2000,
ISBN: 3-540-66422-X.
-
Mok-Kong Shen,
Algorithm 202:
Generation of Permutations in Lexicographical Order,
Communications of the ACM,
Volume 6, Number 9, September 1963, page 517.
-
Richard Stanley,
Hipparchus, Plutarch, Schroeder, and Hough,
American Mathematical Monthly,
Volume 104, Number 4, April 1997, pages 344-350.
-
Dennis Stanton, Dennis White,
Constructive Combinatorics,
Springer, 1986,
ISBN: 0387963472.
-
Ian Stewart,
A Neglected Number,
Scientific American,
Volume 274, pages 102-102, June 1996.
-
Ian Stewart,
Math Hysteria,
Oxford, 2004,
ISBN: 0198613369.
-
James Sylvester,
Question 7382,
Mathematical Questions with their Solutions,
Educational Times,
Volume 41, page 21, 1884.
-
Hale Trotter,
Algorithm 115:
PERM,
Communications of the Association for Computing Machinery,
Volume 5, 1962, pages 434-435.
-
Johannes vanderCorput,
Verteilungsfunktionen I & II,
Proceedings of the Koninklijke Nederlandsche Akademie
van Wetenschappen,
Volume 38, 1935, pages 813-820, pages 1058-1066.
-
Jack vanLint, Richard Wilson,
A Course in Combinatorics,
Cambridge, 1992,
ISBN: 0-521-42260-4.
-
Eric Weisstein,
CRC Concise Encyclopedia of Mathematics,
CRC Press, 2002,
Second edition,
ISBN: 1584883472,
LC: QA5.W45
-
ML Wolfson, HV Wright,
ACM Algorithm 160: Combinatorial of M Things Taken N at a Time,
Communications of the ACM,
Volume 6, Number 4, April 1963, page 161.
-
Stephen Wolfram,
The Mathematica Book,
Fourth Edition,
Cambridge University Press, 1999,
ISBN: 0-521-64314-7,
LC: QA76.95.W65.
-
Daniel Zwillinger, editor,
CRC Standard Mathematical Tables and Formulae,
30th Edition,
CRC Press, 1996,
ISBN: 0-8493-2479-3.
Source Code:
Examples and Tests:
List of Routines:
-
ASM_ENUM returns the number of alternating sign matrices of a given order.
-
ASM_TRIANGLE returns a row of the alternating sign matrix triangle.
-
BELL returns the Bell numbers from 0 to N.
-
BELL_VALUES returns some values of the Bell numbers for testing.
-
BINARY_VECTOR_NEXT generates the next binary vector.
-
BVEC_ADD adds two (signed) binary vectors.
-
BVEC_AND computes the AND of two binary vectors.
-
BVEC_CHECK checks a binary vector.
-
BVEC_COMPLEMENT2 computes the two's complement of a binary vector.
-
BVEC_MUL computes the product of two binary vectors.
-
BVEC_NEXT generates the next binary vector.
-
BVEC_NOT "negates" or takes the 1's complement of a binary vector.
-
BVEC_OR computes the inclusive OR of two binary vectors.
-
BVEC_PRINT prints a binary integer vector, with an optional title.
-
BVEC_REVERSE reverses a binary vector.
-
BVEC_SUB subtracts two binary vectors.
-
BVEC_TO_I4 makes an integer from a (signed) binary vector.
-
BVEC_XOR computes the exclusive OR of two binary vectors.
-
CATALAN computes the Catalan numbers, from C(0) to C(N).
-
CATALAN_ROW_NEXT computes row N of Catalan's triangle.
-
CATALAN_VALUES returns some values of the Catalan numbers for testing.
-
CFRAC_TO_RAT converts a monic continued fraction to an ordinary fraction.
-
CFRAC_TO_RFRAC converts polynomial fractions from continued to rational form.
-
CH_CAP capitalizes a single character.
-
CHANGE_GREEDY makes change for a given total using the biggest coins first.
-
CHANGE_NEXT computes the next set of change for a given sum.
-
CHINESE_CHECK checks the Chinese remainder moduluses.
-
CHINESE_TO_I4 converts a set of Chinese remainders to an equivalent integer.
-
COMB_NEXT computes combinations of K things out of N.
-
COMB_ROW computes row N of Pascal's triangle.
-
COMB_UNRANK returns the RANK-th combination of N things out of M.
-
COMBIN computes the combinatorial coefficient C(N,K).
-
COMBIN2 computes the binomial coefficient C(N,K).
-
COMP_ENUM returns the number of compositions of the integer N into K parts.
-
COMP_NEXT computes the compositions of the integer N into K parts.
-
COMP_RANDOM selects a random composition of the integer N into K parts.
-
COMPNZ_ENUM returns the number of nonzero compositions of the N into K parts.
-
COMPNZ_NEXT computes the compositions of the integer N into K nonzero parts.
-
COMPNZ_RANDOM selects a random composition of N into K nonzero parts.
-
CONGRUENCE solves a congruence of the form A * X = C ( mod B ).
-
COUNT_POSE_RANDOM poses a problem for the game "The Count is Good"
-
DEBRUIJN constructs a de Bruijn sequence.
-
DEC_ADD adds two decimal quantities.
-
DEC_DIV divides two decimal values.
-
DEC_MUL multiplies two decimals.
-
DEC_ROUND rounds a decimal fraction to a given number of digits.
-
DEC_TO_R8 converts a decimal to an R8.
-
DEC_TO_RAT converts a decimal to a rational representation.
-
DEC_TO_S returns a string representation of a decimal.
-
DEC_WIDTH returns the "width" of a decimal number.
-
DECMAT_DET finds the determinant of an N by N matrix of decimal entries.
-
DECMAT_PRINT prints out decimal vectors and matrices.
-
DERANGE_BACK_CANDIDATE finds possible values for the K-th entry of a derangement.
-
DERANGE_BACK_NEXT returns the next derangement of N items.
-
DERANGE_CHECK determines whether a permutation is a derangement.
-
DERANGE_ENUM returns the number of derangements of N objects.
-
DERANGE_ENUM2 returns the number of derangements of 0 through N objects.
-
DERANGE_ENUM3 returns the number of derangements of 0 through N objects.
-
DERANGE_WEED_NEXT computes all of the derangements of N objects, one at a time.
-
DIGIT_TO_CH returns the character representation of a decimal digit.
-
DIGRAPH_ARC_EULER returns an Euler circuit in a digraph.
-
DIGRAPH_ARC_PRINT prints out a digraph from an edge list.
-
DIOPHANTINE solves a Diophantine equation A * X + B * Y = C.
-
DIOPHANTINE_SOLUTION_MINIMIZE seeks a minimal solution of a Diophantine equation.
-
DVEC_ADD adds two (signed) decimal vectors.
-
DVEC_COMPLEMENTX computes the ten's complement of a decimal vector.
-
DVEC_MUL computes the product of two decimal vectors.
-
DVEC_PRINT prints a decimal integer vector, with an optional title.
-
DVEC_SUB subtracts two decimal vectors.
-
DVEC_TO_I4 makes an integer from a (signed) decimal vector.
-
EQUIV_NEXT computes the partitions of a set one at a time.
-
EQUIV_NEXT2 computes, one at a time, the partitions of a set.
-
EQUIV_PRINT prints a partition of a set.
-
EQUIV_RANDOM selects a random partition of a set.
-
EULER returns the N-th row of Euler's triangle.
-
FROBENIUS_NUMBER_ORDER2 returns the Frobenius number for order 2.
-
FROBENIUS_NUMBER_ORDER2_VALUES returns values of the order 2 Frobenius number.
-
GAMMA_LOG calculates the natural logarithm of GAMMA ( X ) for positive X.
-
GAMMA_LOG_VALUES returns some values of the Log Gamma function.
-
GET_SEED returns a seed for the random number generator.
-
GRAY_NEXT generates the next Gray code by switching one item at a time.
-
GRAY_RANK ranks a Gray code.
-
GRAY_RANK2 ranks a Gray code.
-
GRAY_UNRANK unranks a Gray code.
-
GRAY_UNRANK2 unranks a Gray code.
-
I4_BCLR returns a copy of an I4 in which the POS-th bit is set to 0.
-
I4_BSET returns a copy of an I4 in which the POS-th bit is set to 1.
-
I4_BTEST returns TRUE if the POS-th bit of an I4 is 1.
-
I4_FACTOR factors an I4 into prime factors.
-
I4_FACTORIAL computes the factorial of N.
-
I4_GCD finds the greatest common divisor of I and J.
-
I4_HUGE returns a "huge" I4.
-
I4_LOG_10 returns the integer part of the logarithm base 10 of an I4.
-
I4_MODP returns the nonnegative remainder of I4 division.
-
I4_MOEBIUS returns the value of MU(N), the Moebius function of N.
-
I4_PARTITION_CONJ computes the conjugate of a partition.
-
I4_PARTITION_COUNT computes the number of partitions of an I4.
-
I4_PARTITION_COUNT2 computes the number of partitions of an I4.
-
I4_PARTITION_COUNT_VALUES returns some values of the integer partition count.
-
I4_PARTITION_NEXT generates the partitions of an I4, one at a time.
-
I4_PARTITION_NEXT2 computes the partitions of the integer N one at a time.
-
I4_PARTITION_PRINT prints a partition of an I4.
-
I4_PARTITION_RANDOM selects a random partition of an integer.
-
I4_PARTITIONS_NEXT: next partition into S parts.
-
I4_RISE computes the rising factorial function [X]^N.
-
I4_SQRT finds the integer square root of N by solving N = Q**2 + R.
-
I4_SQRT_CF finds the continued fraction representation of a square root of an integer.
-
I4_SWAP switches two I4's.
-
I4_TO_BVEC makes a signed binary vector from an I4.
-
I4_TO_CHINESE converts an I4 to its Chinese remainder form.
-
I4_TO_DVEC makes a signed decimal vector from an I4.
-
I4_TO_I4POLY converts an I4 to an I4POLY in a given base.
-
I4_TO_S_LEFT converts an I4 to a left-justified string.
-
I4_TO_VAN_DER_CORPUT computes an element of a van der Corput sequence.
-
I4_UNIFORM returns a scaled pseudorandom I4.
-
I4MAT_01_ROWCOLSUM creates a 0/1 I4MAT with given row and column sums.
-
I4MAT_01_ROWCOLSUM2 creates a 0/1 I4MAT with given row and column sums.
-
I4MAT_PERM permutes the rows and columns of a square I4MAT.
-
I4MAT_PERM2 permutes the rows and columns of a rectangular I4MAT.
-
I4MAT_PRINT prints an I4MAT.
-
I4MAT_PRINT_SOME prints some of an I4MAT.
-
I4MAT_U1_INVERSE inverts a unit upper triangular matrix.
-
I4POLY performs operations on I4POLY's in power or factorial form.
-
I4POLY_CYCLO computes a cyclotomic polynomial.
-
I4POLY_DEGREE returns the degree of an I4POLY.
-
I4POLY_DIV computes the quotient and remainder of two I4POLY's.
-
I4POLY_MUL computes the product of two I4POLY's.
-
I4POLY_PRINT prints an I4POLY.
-
I4POLY_TO_I4 evaluates an I4POLY.
-
I4VEC_ASCENDS determines if an I4VEC is (weakly) ascending.
-
I4VEC_BACKTRACK supervises a backtrack search for an I4VEC.
-
I4VEC_COPY copies an I4VEC.
-
I4VEC_DESCENDS determines if an I4VEC is (weakly) descending.
-
I4VEC_FRAC searches for the K-th smallest element in an I4VEC.
-
I4VEC_INDICATOR sets an I4VEC to the indicator vector.
-
I4VEC_INDEX returns the location of the first occurrence of a given value.
-
I4VEC_MAX computes the maximum element of an I4VEC.
-
I4VEC_MAXLOC_LAST returns the index of the last maximal I4VEC entry.
-
I4VEC_MIN computes the minimum element of an I4VEC.
-
I4VEC_PAIRWISE_PRIME checks whether an I4VEC's entries are pairwise prime.
-
I4VEC_PRINT prints an I4VEC.
-
I4VEC_PRINT_SOME prints "some" of an I4VEC.
-
I4VEC_PRODUCT returns the product of the entries of an I4VEC.
-
I4VEC_REVERSE reverses the elements of an I4VEC.
-
I4VEC_SORT_BUBBLE_A ascending sorts an I4VEC using bubble sort.
-
I4VEC_SORT_HEAP_INDEX_D does an indexed heap descending sort of an I4VEC.
-
I4VEC_SUM returns the sum of the entries of an I4VEC.
-
I4VEC_TRANSPOSE_PRINT prints an I4VEC "transposed".
-
I4VEC_UNIFORM returns a scaled pseudorandom I4VEC.
-
I4VEC_ZERO sets the entries of an I4VEC to 0.
-
INDEX_BOX2_NEXT_2D produces index vectors on the surface of a box in 2D.
-
INDEX_BOX2_NEXT_3D produces index vectors on the surface of a box in 3D.
-
INDEX_BOX_NEXT_2D produces index vectors on the surface of a box in 2D.
-
INDEX_BOX_NEXT_3D produces index vectors on the surface of a box in 3D.
-
INDEX_NEXT0 generates all index vectors within given upper limits.
-
INDEX_NEXT1 generates all index vectors within given upper limits.
-
INDEX_NEXT2 generates all index vectors within given lower and upper limits.
-
INDEX_RANK0 ranks an index vector within given upper limits.
-
INDEX_RANK1 ranks an index vector within given upper limits.
-
INDEX_RANK2 ranks an index vector within given lower and upper limits.
-
INDEX_UNRANK0 unranks an index vector within given upper limits.
-
INDEX_UNRANK1 unranks an index vector within given upper limits.
-
INDEX_UNRANK2 unranks an index vector within given lower and upper limits.
-
INS_PERM computes a permutation from its inversion sequence.
-
INVERSE_MOD_N computes the inverse of B mod N.
-
INVOLUTE_ENUM enumerates the involutions of N objects.
-
JFRAC_TO_RFRAC converts a J-fraction into a rational polynomial fraction.
-
JOSEPHUS returns the position X of the K-th man to be executed.
-
KSUB_NEXT generates the subsets of size K from a set of size N.
-
KSUB_NEXT2 generates the subsets of size K from a set of size N.
-
KSUB_NEXT3 generates the subsets of size K from a set of size N.
-
KSUB_NEXT4 generates the subsets of size K from a set of size N.
-
KSUB_RANDOM selects a random subset of size K from a set of size N.
-
KSUB_RANDOM2 selects a random subset of size K from a set of size N.
-
KSUB_RANDOM3 selects a random subset of size K from a set of size N.
-
KSUB_RANDOM4 selects a random subset of size K from a set of size N.
-
KSUB_RANK computes the rank of a K subset of an N set.
-
KSUB_UNRANK returns the subset of a given rank.
-
Purpose:
-
MATRIX_PRODUCT_OPT determines the optimal cost of a matrix product.
-
MOEBIUS_MATRIX finds the Moebius matrix from a covering relation.
-
MORSE_THUE generates a Morse_Thue number.
-
MULTINOMIAL_COEF1 computes a multinomial coefficient.
-
MULTINOMIAL_COEF2 computes a multinomial coefficient.
-
NETWORK_FLOW_MAX finds the maximal flow and a minimal cut in a network.
-
NIM_SUM computes the Nim sum of two integers.
-
PADOVAN returns the first N values of the Padovan sequence.
-
PELL_BASIC returns the fundamental solution for Pell's basic equation.
-
PELL_NEXT returns the next solution of Pell's equation.
-
PENT_ENUM computes the N-th pentagonal number.
-
PERM_ASCEND computes the longest ascending subsequence of a permutation.
-
PERM_BREAK_COUNT counts the number of "breaks" in a permutation.
-
PERM_CANON_TO_CYCLE converts a permutation from canonical to cycle form.
-
PERM_CHECK checks that a vector represents a permutation.
-
PERM_CYCLE analyzes a permutation.
-
PERM_CYCLE_TO_CANON converts a permutation from cycle to canonical form.
-
PERM_CYCLE_TO_INDEX converts a permutation from cycle to standard index form.
-
PERM_DISTANCE computes the Ulam metric distance of two permutations.
-
PERM_FIXED_ENUM enumerates the permutations of N objects with M fixed.
-
PERM_FREE reports the unused items in a partial permutation.
-
PERM_INDEX_TO_CYCLE converts a permutation from standard index to cycle form.
-
PERM_INS computes the inversion sequence of a permutation.
-
PERM_INVERSE inverts a permutation "in place".
-
PERM_INVERSE2 inverts a permutation "in place".
-
PERM_INVERSE3 produces the inverse of a given permutation.
-
PERM_LEX_NEXT generates permutations in lexical order, one at a time.
-
PERM_MUL "multiplies" two permutations.
-
PERM_NEXT computes all of the permutations of N objects, one at a time.
-
PERM_NEXT2 generates all the permutations of N objects.
-
PERM_NEXT3 computes all of the permutations of N objects, one at a time.
-
PERM_PRINT prints a permutation.
-
PERM_RANDOM selects a random permutation of N objects.
-
PERM_RANDOM2 selects a random permutation of N objects.
-
PERM_RANDOM3 selects a random permutation of N elements.
-
PERM_RANK computes the rank of a given permutation.
-
PERM_SIGN returns the sign of a permutation.
-
PERM_TO_EQUIV computes the partition induced by a permutation.
-
PERM_TO_YTB converts a permutation to a Young table.
-
PERM_UNRANK "unranks" a permutation.
-
PERRIN returns the first N values of the Perrin sequence.
-
PORD_CHECK checks a matrix representing a partial ordering.
-
POWER_MOD computes mod ( A**N, M ).
-
POWER_SERIES1 computes the power series for G(Z) = (1+F(Z))**ALPHA.
-
POWER_SERIES2 computes the power series for G(Z) = exp(F(Z)) - 1.
-
POWER_SERIES3 computes the power series for H(Z) = G(F(Z)).
-
POWER_SERIES4 computes the power series for H(Z) = G ( 1/F(Z) ).
-
PRIME returns any of the first PRIME_MAX prime numbers.
-
PYTHAG_TRIPLE_NEXT computes the next Pythagorean triple.
-
R8_AGM finds the arithmetic-geometric mean of two numbers.
-
R8_EPSILON returns the R8 roundoff unit.
-
R8_FACTORIAL computes the factorial of N.
-
R8_FALL computes the falling factorial function [X]_N.
-
R8_HUGE returns a "huge" R8.
-
R8_IS_INT determines if an R8 represents an integer value.
-
R8_PI returns the value of pi as an R8.
-
R8_RISE computes the rising factorial function [X]^N.
-
R8_SWAP switches two R8's.
-
R8_TO_CFRAC converts a real value to a continued fraction.
-
R8_TO_DEC converts a real quantity to a decimal representation.
-
R8_TO_RAT converts a real value to a rational value.
-
R8_TO_S_LEFT represents a real using 14 left_justified characters.
-
R8_UNIFORM returns a scaled pseudorandom R8.
-
R8_UNIFORM_01 returns a unit pseudorandom R8.
-
R8MAT_DET finds the determinant of an N by N R8MAT.
-
R8MAT_PERM permutes the rows and columns of a square R8MAT.
-
R8MAT_PERM2 permutes rows and columns of a rectangular R8MAT, in place.
-
R8MAT_PERMANENT computes the permanent of an R8MAT.
-
R8MAT_PRINT prints an R8MAT.
-
R8MAT_PRINT_SOME prints some of an R8MAT.
-
R8POLY performs operations on real polynomials in power or factorial form.
-
R8POLY_DEGREE returns the degree of a polynomial in power sum form.
-
R8POLY_DIV computes the quotient and remainder of two polynomials.
-
R8POLY_F2P converts a real polynomial from factorial form to power sum form.
-
R8POLY_FVAL evaluates a real polynomial in factorial form.
-
R8POLY_MUL computes the product of two real polynomials A and B.
-
R8POLY_N2P converts a real polynomial from Newton form to power sum form.
-
R8POLY_NVAL evaluates a real polynomial in Newton form.
-
R8POLY_NX replaces one of the base points in a polynomial in Newton form.
-
R8POLY_P2F converts a real polynomial from power sum form to factorial form.
-
R8POLY_P2N converts a real polynomial from power sum form to Newton form.
-
R8POLY_P2T converts a real polynomial from power sum form to Taylor form.
-
R8POLY_POWER computes a positive integer power of a polynomial.
-
R8POLY_PRINT prints out a polynomial.
-
R8POLY_PVAL evaluates a real polynomial in power sum form.
-
R8POLY_T2P converts a real polynomial from Taylor form to power sum form.
-
R8VEC_BACKTRACK supervises a backtrack search for an R8VEC.
-
R8VEC_FRAC searches for the K-th smallest entry in an R8VEC.
-
R8VEC_INDICATOR sets an R8VEC to the indicator vector.
-
R8VEC_MIRROR_NEXT steps through all sign variations of an R8VEC.
-
R8VEC_PRINT prints an R8VEC.
-
R8VEC_UNIFORM returns a scaled pseudorandom R8VEC.
-
R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
-
RAT_ADD adds two rational values.
-
RAT_DIV divides one rational value by another.
-
RAT_FAREY computes the N-th row of the Farey fraction table.
-
RAT_FAREY2 computes the next row of the Farey fraction table.
-
RAT_MUL multiplies two fractions.
-
RAT_NORMALIZE normalizes a rational number.
-
RAT_SUM_FORMULA computes the formulas for sums of powers of integers.
-
RAT_TO_CFRAC converts a rational value to a continued fraction.
-
RAT_TO_DEC converts a rational to a decimal representation.
-
RAT_TO_R8 converts rational values to real values.
-
RAT_TO_S_LEFT returns a left-justified representation of A/B.
-
RAT_WIDTH returns the "width" of a rational number.
-
RATMAT_DET finds the determinant of an N by N matrix of rational entries.
-
RATMAT_PRINT prints out rational vectors or matrices.
-
REGRO_NEXT computes restricted growth functions one at a time.
-
RFRAC_TO_CFRAC converts a rational polynomial fraction to a continued fraction.
-
RFRAC_TO_JFRAC converts a rational polynomial fraction to a J fraction.
-
S_ADJUSTR flushes a string right.
-
S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
-
S_BLANKS_DELETE replaces consecutive blanks by one blank.
-
S_EQI is a case insensitive comparison of two strings for equality.
-
S_LEN_TRIM returns the length of a string to the last nonblank.
-
SCHROEDER generates the Schroeder numbers.
-
SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
-
SUB_BY_SIZE_NEXT returns all subsets of an N set, in order of size.
-
SUB_GRAY_NEXT generates all subsets of a set of order N, one at a time.
-
SUB_GRAY_RANK ranks a subset of an N set, using the Gray code ordering.
-
SUB_GRAY_UNRANK produces a subset of an N set of the given Gray code rank.
-
SUB_LEX_NEXT generates the subsets of a set of N elements, one at a time.
-
SUB_RANDOM selects a random subset of an N-set.
-
SUBCOMP_NEXT computes the next subcomposition of N into K parts.
-
SUBCOMPNZ_NEXT computes the next subcomposition of N into K nonzero parts.
-
SUBCOMPNZ2_NEXT computes the next subcomposition of N into K nonzero parts.
-
THUE_BINARY_NEXT returns the next element in a binary Thue sequence.
-
THUE_TERNARY_NEXT returns the next element in a ternary Thue sequence.
-
TIMESTAMP prints out the current YMDHMS date as a timestamp.
-
TIMESTRING writes the current YMDHMS date into a string.
-
TRIANG renumbers elements in accordance with a partial ordering.
-
TUPLE_NEXT computes the next element of a tuple space.
-
TUPLE_NEXT_FAST computes the next element of a tuple space, "fast".
-
TUPLE_NEXT_GE computes the next "nondecreasing" element of a tuple space.
-
TUPLE_NEXT2 computes the next element of an integer tuple space.
-
UBVEC_ADD adds two unsigned binary vectors.
-
UBVEC_TO_UI4 makes an unsigned integer from an unsigned binary vector.
-
UI4_TO_UBVEC makes an unsigned binary vector from an unsigned integer.
-
VEC_NEXT generates all N-vectors of integers modulo a given base.
-
VEC_NEXT_GRAY computes the elements of a product space.
-
VEC_RANDOM selects a random N-vector of integers modulo a given base.
-
VEC_RANK computes the rank of a product space element.
-
VEC_UNRANK computes the product space element of a given rank.
-
VECTOR_CONSTRAINED_NEXT returns the "next" constrained vector.
-
VECTOR_CONSTRAINED_NEXT2 returns the "next" constrained vector.
-
VECTOR_CONSTRAINED_NEXT3 returns the "next" constrained vector.
-
VECTOR_CONSTRAINED_NEXT4 returns the "next" constrained vector.
-
VECTOR_CONSTRAINED_NEXT5 returns the "next" constrained vector.
-
VECTOR_CONSTRAINED_NEXT6 returns the "next" constrained vector.
-
VECTOR_CONSTRAINED_NEXT7 returns the "next" constrained vector.
-
VECTOR_NEXT returns the "next" vector between two ranges.
-
YTB_ENUM enumerates the Young tables of size N.
-
YTB_NEXT computes the next Young table for a given shape.
-
YTB_PRINT prints a Young table.
-
YTB_RANDOM selects a random Young table of a given shape.
You can go up one level to
the FORTRAN77 source codes.
Last revised on 03 August 2010.