multiset combinations of k out of n (n multichoose k)
This library implements an efficient loopless multiset combination generation algorithm which is (approximately) described in "Loopless algorithms for generating permutations, combinations, and other combinatorial configurations." G Ehrlich - Journal of the ACM (JACM), 1973. (Algorithm 7.)
The method generates all multisets that would be generated from taking k elements from a multiset of n. Repeated multisets are possible if the input set contains repeated elements. The number of multiset combinations equals the multinomial coefficient (n multichoose k).
npm install -g multichoose
var multichoose =// [ 1, 1 ]// [ 1, 2 ]// [ 1, 3 ]// [ 2, 2 ]// [ 2, 3 ]// [ 3, 3 ]
% multichoose 3 A B CA A AA A BA A CA B BA B CA C CB B BB B CB C CC C C
Include is a C++ library/program which contains a generic function to generate multisets for vectors of any type of object. You can test out the program using strings input from the command line by typing:
Running the bare executable prints usage information:
% ./multichooseusage:./multichoose <k> <item1> <item2> ... <itemN> ~ n multichoose k
% ./multichoose 2 a t g ca aa ta ga ct tt gt cg gg cc c
This example lists all the possible unordered genotypes at a given genetic loci of which there are two copies (e.g. chromosomes). In this case
k (=2) could be understood as the expected ploidy of the given locus.
(Note that this is not currently built as the default binary for the npm module, which uses cli.js.)
A python library implementation is also included for those who like to indent their code consistently.
TODO: These will be factored into a separate module.