Libraries C/C++ for ordered combinations generation and ranking/unranking ?

Question

Hello, I'm looking for a library which could rank/unrank ordered combinations (ranking means from a combination it give you which nth combinations it is from a gray code or lexicographic or some other algorithm, unranking is the reversing process).

I look for a library doing many algorithmes like gray code or lexicographic, rev-lexicographic, enup and so on...)

If it does only generation it can be ok but with many algorithms too.

I found FXT library but it does not use ordered combinations(it does compositions but it seems not to do algorithm of ranking as i need it, it's comparable to rank/unrank unordered combinations).

thanks.

Answer 1

It's not quite an answer to your question, but there is an excellent book on exactly this topic called "Combinatorial Algorithms : Generation, Enumeration, And Search"

http://www.math.mtu.edu/~kreher/cages.html

it's nicely balanced between the algorithmic/mathematical side, and actual implementation. Most of the examples are simple enough that they can be written in a procedural language like c in a very short amount of time.

Answer 2

do you need something like this:

// get a combination of a rank // n number k choices N rank

void unrankComb(int* &K, int n, int k, int N) { int e, N2, t, m, p;

e = nCr(n,k); N2 = e-1-N; e = ((n - k)*e)/n; t = n - k + 1; m = k; p = n -1; do { if(e <= N2) { K[k-m] = n - t - m + 2; if(e > 0) { N2 = N2 -e; e = (e * m) / p; } m = m -1; p = p -1; } else { e = ((p - m)*e) / p; t = t - 1; p = p - 1; }

}while(m != 0); }