#ifndef _COMBINATORICS_H
#define _COMBINATORICS_H
#include "misc.h"

/*
** These functions will return all the actual combinations of n choose m
** integers, in the array A that you supply.  CombinNext returns 0 when
** there are no more. For example, asking for Choose(5,3) will return 10 times,
** populating 3 elements of the array each time with the following elements:
** {012 013 014 023 024 034 123 124 134 234}
*/
typedef struct _combin {
    unsigned n, m, *array;
} COMBIN;

COMBIN *CombinZeroth(int n, int m, unsigned *array);
/* IthCombination skips the first I combinations (numbered from 0) */
COMBIN *CombinIth(int N, int M, unsigned *A, unsigned long long I);
Boolean CombinSkipN(COMBIN *, int n);   /* very dumb implementation */
Boolean CombinNext(COMBIN*);
Boolean CombinAssign(COMBIN *c, unsigned newCombin[c->m]);

/*
** Call this when you are done with a (COMBIN*).
** Since you supplied the array, you are responsible to free it if necessary.
*/
#define CombinFree Free

/*
** Just counts the number of M-subsets from a set of size N.
** This is a tad slow, using an O(m*(n-m)) algorithm to drastically reduce
** frequency of intermediate overflows. 
*/
unsigned long long CombinChoose(int n, int m);

/*
** See p. -53 of Thesis Book 1.  The following two are the "Cumulative
** Binomial Distribution", and it's derivative which is the density
** function.  It represents the distribution of the kth sorted RV out
** n chosen from a uniform (0,1) distribution.
**
** F^n_k(x) = \sum_{j=k}^n x^j(1-x)^{n-j}\Choose{n,j}
** D(") = f^n_k(x) = x^{-1} (1-x)^{n-1} \sum_{j=k}^n
**                         \Choose{n,j} (x/(1-x))^j (j-nx)
*/
double CombinCumulativeBinomialCumulative(int n, int k, double x);
double CombinCumulativeBinomialDensity(int n, int k, double x);

/*
** AllCombinations will call (*fcn)(m, [m-sized array]) once for each possible
** combination of m integers out of 0..n-1 inclusive.
** AllPermutations will call (*fcn)(n, [n-sized array]) once for each of 
** all n! permutations of the integers 0..n-1 inclusive.
** In both cases, (*fcn) should return 0 if the iterations should continue, or
** non-zero otherwise.  The return value of All* will be 0 if we went through
** all sets, otherwise it will be the return value of (*fcn) that caused us
** to stop.  These are probably less useful than the First*, Next* functions
** defined above, but were easier to write so I wrote them first.
*/

Boolean CombinAllCombinations(int n, int m, Boolean (*fcn)(int, int *));
Boolean CombinAllPermutations(int n, Boolean (*fcn)(int, int *));

#endif /* _COMBINATORICS_H */
