VChooseK

version 1.0.0.0 (13.7 KB) by Jan
Choose K elements from a vector - MEX: 100 times faster than NCHOOSEK

3K Downloads

Updated 23 Dec 2009

View License

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.

Cite As

Jan (2022). VChooseK (https://www.mathworks.com/matlabcentral/fileexchange/26190-vchoosek), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2009a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!