Code covered by the BSD License  

Highlights from
VChooseK

5.0

5.0 | 5 ratings Rate this file 41 Downloads (last 30 days) File Size: 13.7 KB File ID: #26190
image thumbnail

VChooseK

by

 

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

| Watch this File

File Information
Description

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.

Acknowledgements

Picking Elements From A Set, N Ctwo, Nchoose2 (V2.1 Jun 2008), Combinations, and Combinator Combinations And Permutations inspired this file.

This file inspired V Choose Ko, Nsumk, and Ichoose.

MATLAB release MATLAB 7.8 (R2009a)
Other requirements This replaces my former FEX submission NChoose2q.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (16)
06 Jul 2014 Jan Simon

@Nitin Agrawal: No, there is no pure C-code. I meant, that you can use the MSVC2010 version to compile the C-mex function. Sorry.

30 Jun 2014 Nitin Agrawal

@Jan. Thanks for your response. In your earlier reply dated 16 feb 2014, you said that the c-code can be compiled using MSV 2010 without any modifications. Is there a pure C version available with you? Could you upload it.

29 Jun 2014 Jan Simon

@Nitin Agrawal: mex.h belongs to Matlab. If you want to use the function in a C-environment, you neither need mex.h nor the gateway function mexFunction(). Some modifications are required, e.g. the functions for the errors and warnings. I'd suggest to start from the inc-file and implement one data type required for your problem only.

29 Jun 2014 Nitin Agrawal

Hi Jan

I wanted the use this code as a C function in one of my C programs, however when I try to compile this code in C (using gcc), headers file "MEX.h" is found to be missing by the compiler. It in turn required me to have "Pair.h" and "matrix.h", <vector> etc when I tried using a "MEX.h" header file which I found on the internet. Please advice.

10 Mar 2014 Timo Eckhard

@Jan: great function!

For those using Linux, you need to compile using:
'mex -O CFLAGS="\$CFLAGS -std=c99" VChooseK.c'

There is a small mistake in the description in 'VChooseK.m', indicating to compile as:
mex CFLAGS="\$CFLAGS -std=C99" -O VChooseK.c

For those who run into an error because attempting to get a too large number of combinations:

-> Edit Line 94 in 'VChooseK.c':
'#define ERROR_LIMIT 1000000000L // 1 GB (recommended for 32&64 bit systems)'
to something bigger. Keep in mind to have enough memory available

-> recompile the source code

Works great, works fast. Just fine for me...

10 Mar 2014 Timo Eckhard

For those who run into an error because attempting to get a too large number of combinations:

-> Edit Line 94 in 'VChooseK.c':
'#define ERROR_LIMIT 1000000000L // 1 GB (recommended for 32&64 bit systems)'
to something bigger. Keep in mind to have enough memory available

-> recompile the source code

Works great, works fast. Just fine for me...

16 Feb 2014 Jan Simon

@Deepak Gawali: You can compile this C-code with MSVC2010 without any modifications.

09 Jan 2014 Deepak Gawali

If I want to use vchoosek.c in visual studio 2010, will it work or do you have other code to use in vs2010.

28 Feb 2013 Alexandros Iliopoulos  
06 Feb 2013 Gabriel Bruneau

Fantastic submission!

For the job I had to do:
nchoosek: 405 seconds
VChooseK: 6.19 seconds

Thanks a lot Jan!

03 Sep 2012 Hassan

Error in compiler
R2012a
No supported SDK or compiler was found on this computer.
For a list of supported compilers, see
http://www.mathworks.com/support/compilers/R2012a/win64.html

Error using mex (line 206)
Unable to complete successfully.

02 May 2012 Kristofer Kusano

This works great, much faster than the built in Matlab function, as advertised. Thanks for sharing your work!

19 Dec 2011 Jan Simon

Dear Mark, before you can use the function, you have to compile it as explained in the documentation:
mex -O VChooseK.c
An explicite message will appear in a future version.

19 Dec 2011 Mark Whirdy

Hi Jan

I went to use this but came across a snag at the first hurdle, have you an idea of where the problem may lie?

==== Test VChooseK: 19-Dec-2011 18:15:35
Version: J:\Financial_Engineering\QUANT FIXED INCOME\...\VChooseK.m

== DOUBLE, K = 1:
Error in ==> VChooseK at 1
function Y = VChooseK(X, K)

??? Output argument "Y" (and maybe others) not assigned during call to "J:\Financial_Engineering\...\VChooseK.m>VChooseK".

Error in ==> TestVChooseK at 66
S = VChooseK(my_cast([], aClass), K);

22 Jan 2010 Jan Simon

For choosing with/without Repitions and Order see also my submissions:
O: http://www.mathworks.com/matlabcentral/fileexchange/26397
R: http://www.mathworks.com/matlabcentral/fileexchange/26277
RO: http://www.mathworks.com/matlabcentral/fileexchange/26242

01 Jan 2010 Jan Simon

I've deleted the file NChoose2q (limited to K==2), because it had no advantages compared with the more general VChooseK. Please mail me, if this causes problems for anybody.

Contact us