VChooseK

Choose K elements from a vector - MEX: 100 times faster than NCHOOSEK

VChooseK(V, K) creates a matrix, which rows are all combinations of choosing K elements of the vector V without order and without repititions.

INPUT:
V: Array of class DOUBLE, SINGLE, (U)INT8/16/32/64, LOGICAL, CHAR.
K: Number of elements to choose.

OUTPUT:
Y: Matrix of size [N!/K!(N-K)!, K] with N is the number of elements of V.
Y has the same class as the input V.

The output equals Matlab's NCHOOSEK, except that NCHOOSEK replies the number of combinations for a scalar V:
VChooseK(-1, 1) replies [-1]: One element taken out of a set of length one.
NCHOOSEK(-1, 1) fails at calculating N!/K!(N-K)!.

EXAMPLES:
Choose 2 elements from [1,2,3,4]:
VChooseK(1:4, 2)
==> [1,2; 1,3; 1,4; 2,3; 2,4; 3,4]
For speed cast the input to integer types if possible:
Y = double(VChooseK(int16(1:1000), 2);
is faster than:
Y = VChooseK(1:1000, 2);
To get the combinations of cell arrays, use the combinations of the index:
C = {'a', 'b', 'c', 'd'};
C2 = C(VChooseK(1:4, 2))
==> C2 = {'a', 'b'; 'a', 'c'; 'a', 'd'; 'b', 'c'; 'b', 'd'; 'c', 'd'}

INSPIRATION:
Jos van der Geest has published an efficient NCHOOSE2, which is much faster than Matlab's NCHOOSEK: http://www.mathworks.com/matlabcentral/fileexchange/20144
I was curious, if a MEX version is much faster. At first I've created NChoose2q, which was 5 times faster than Jos' Matlab implementation. But the algorithm was so simple in C and did not consume temporary memory, that I've expanded it to K=3,4,5 soon. The algorithm for free K was more challenging, but it needs just 3*K pointers for temporary memory. Therefore it is much faster than Matlab's NCHOOSEK (Matlab 7.8, 1.5GHz Pentium-M, 512 MB):
NCHOOSEK(1:50, 5): 45.30 sec
VChooseK(1:50, 5): 0.32 sec => 141 times faster
NCHOOSEK(1:20, 16): 0.52 sec
VChooseK(1:20, 16) 0.0024 sec => 216 times faster
NCHOOSEK(int8(1:40), 4): 0.64 sec
VChooseK(int8(1:40), 4): 0.001562 sec => 410 times faster

The powerful COMBINATOR of Matt Fig handles repititions and ordered sequences also, but for its specific job VChooseK is remarkably faster (see screen shot).

Tested: Matlab 6.5, 7.7, 7.8, WinXP
Compilers: BCC5.5, LCC2.4/3.8, Open Watcom 1.8
Please run the unit-test TestVChooseK after compiling and for speed comparisons.