Code covered by the BSD License  

Highlights from
COMBINATOR -combinations AND permutations

4.94444

4.9 | 18 ratings Rate this file 120 Downloads (last 30 days) File Size: 32.7 KB File ID: #24325
image thumbnail

COMBINATOR -combinations AND permutations

by

 

02 Jun 2009 (Updated )

Returns 1 of 4 different samplings on the set 1:N, taken K at a time.

| Watch this File

File Information
Description

COMBINATOR will return one of 4 different samplings on the set 1:N, taken K at a time. These samplings are given as follows:
   
PERMUTATIONS WITH REPETITION/REPLACEMENT
  COMBINATOR(N,K,'p','r') -- N >= 1, K >= 0

PERMUTATIONS WITHOUT REPETITION/REPLACEMENT
  COMBINATOR(N,K,'p') -- N >= 1, N >= K >= 0

COMBINATIONS WITH REPETITION/REPLACEMENT
  COMBINATOR(N,K,'c','r') -- N >= 1, K >= 0

COMBINATIONS WITHOUT REPETITION/REPLACEMENT
  COMBINATOR(N,K,'c') -- N >= 1, N >= K >= 0

Example:

combinator(4,2,'p','r') % Permutations with repetition
combinator(4,2,'p') % Permutations without repetition
combinator(4,2,'c','r') % Combinations with repetition
combinator(4,2,'c') % Combinations without repetition
ans =
     1 1
     1 2
     1 3
     1 4
     2 1
     2 2
     2 3
     2 4
     3 1
     3 2
     3 3
     3 4
     4 1
     4 2
     4 3
     4 4
ans =
     1 2
     1 3
     1 4
     2 1
     2 3
     2 4
     3 1
     3 2
     3 4
     4 1
     4 2
     4 3
ans =
     1 1
     1 2
     1 3
     1 4
     2 2
     2 3
     2 4
     3 3
     3 4
     4 4
ans =
     1 2
     1 3
     1 4
     2 3
     2 4
     3 4

The accompanying c++ file can be MEXed to provide the ability to specify N as an int8, int16, or int32. This saves memory and is faster. I have provided a MEX file that was created on Win XP with 2006a that may work. If not, the file will need to be MEXed on your machine.
Please READ the help before using.
I would very much appreciate bug reports sent through email, as well as suggestions for improvement. Thanks.

Acknowledgements

This file inspired V Choose K, V Choose Kro, V Choose Kr, V Choose Ko, Ichoose, and Generates Test Sample(Audio).

MATLAB release MATLAB 7.4 (R2007a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (32)
08 Aug 2014 mohammad

please any help

03 Aug 2014 mohammad

please , help me

01 Aug 2014 mohammad

my friend , i have a problem when performing your program that's:
clc
clear
A=[1:29];
A=A(:);
combs = A(combinator(29,28,'c'))
when K is 28 the function is working well but when K is 27 combs = A(combinator(29,27,'c')) MATLAB gives me error:

combs = A(combinator(29,27,'c'))
Subscript indices must either be real positive integers or logicals.

from K=26 to 23 the function works normally and perfectly but K=22
combs = A(combinator(29,22,'c'))
Subscript indices must either be real positive integers or logicals.

and :
combs = A(combinator(29,21,'c'))
Subscript indices must either be real positive integers or
logicals.

and:when K=20
combs = A(combinator(29,20,'c'))
my computer become very heavy where I was forced to get out of the program

i don't complete the rest of numbers so that know what will happen with them

please Matt fig , how can i solve these problems ?
i want to tell you that i have vectors contain more than 1000 numbers not 29 numbers only and i will do this processes on them

03 Jul 2014 Shane

Very helpful! A little scary to work with, because things get real big real fast, but this package deals with a difficult problem with great efficiency.

25 May 2014 pouya jamali  
23 May 2014 Say Cook

Is there a version of this that allows for generating each combination (ex. each row in the matrix) in a loop, instead of generating one big matrix?

I have a large number of combinations to consider, of which I would only be saving a subset of them, and don't need the matrix at once (it would be too big anyways)... Thanks.

23 May 2014 Claudio

ATTENTION!

Tough the package is excellent and I will rate it with 5 stars, there is a BUG in the code involving a high number of combinations in that the last row is filled of zeros.

almacellesiti Fernandez pointed out the solution to the bug. Replace the following line

BC=prod(M-K+1:M) / (prod(1:K));

with

BC=round(prod(M-K+1:M) / (prod(1:K)));

and it works fine.

05 Nov 2013 Matt Fig

Alesya,

That is a memory limitation on your computer. You are asking MATLAB to build a matrix that is (5^13)-by-13. This is a matrix with nearly 16 billion entries. In double precision this would require over 100 GB of RAM!

You probably need to do something different for your particular application.

03 Nov 2013 Alesya

Thank you for such great work!
But I have a little problem. When I use this command
M = combinator(5,13,'p','r')
I get the foolowing error:

"??? Error using ==> zeros
Out of memory. Type HELP MEMORY for your options.
Error in ==> combinator>perms_rep at 155
PR = zeros(L,K,CN); % Preallocation.
Error in ==> combinator at 110
A = perms_rep(N,K); % strings"

Could you check what is wrong? Is it possible to avoid this error?

04 Sep 2013 Mauricio

Impressive, never thought I can finds something like this. So intuitive, comprehensive and simple to use. Real life saver

27 Apr 2013 Peter

Created a newsgroup profile just to add this rating!

13 Dec 2012 SAQIB

Excellent work

29 Oct 2012 MARIO CASTRO GAMA

is excellent, very fast!

15 Jun 2012 Vitor F. C.

Excellent job, you saved my phd! :)

15 Jun 2012 Vitor F. C.  
17 Apr 2012 7ate9

Works well for the few tests I ran. Had to compile for 64 bit, but that was painless. Thanks!

29 Aug 2011 Xavier

Great code, very fast and just what I needed... but I'm getting an error on the output data when I run the following case:

COMBINATOR(50,n,'c')

the last line has only zeros when n is 46 or 47, but not when it is 44, 45 or 48.

Can you check what's wrong?

25 May 2011 mortain Antonio

Hey Matt, I came back on your software and I found a changed a value of the original one that's why it was giving the error. It's an amazing software...clear and so elegant!

Thank you very much

10 Apr 2011 Chien-Chia Huang

Thanks a lot, Matt.
It does help.

23 Sep 2010 Stephan Schmidt

Great package, exactly what I needed for http://www.mathworks.de/matlabcentral/newsreader/view_thread/292210

Thanks a lot Matt!

10 Aug 2010 Matt Fig

Oops, that was an error of omission on my part. I will post an update. Thanks Jan.

09 Aug 2010 Jan Simon

Your first submission contained the source code cumsumall.cpp. Now I find only the compiled mexw32. It would be nice to have the source again, to allow all non-Windows and the 64 bitters to work with COMBINATOR.

22 Jun 2010 almacellesiti Fernandez

Nice one Matt.

There might be a small problem though. With matlab 2009 in windows and matlab 2008 in linux I can reproduce the following problem.

combinator(24,23,'c')

leaves the last row of the return matrix to zeros. It does not update it because the parameter

BC=prod(M-K+1:M) / (prod(1:K));

inside the function function CN = combs_no_rep(N,K), at the line 343 of combinator.m

results in BC=23.999999999999996 (instead of the correct value, 24)

I guess a round in that line will take care of it.
A few other combinations of numbers give no problem.

02 Mar 2010 Tal Shir

Just what I needed. Thanks.

13 Jan 2010 Jan Simon

Another idea: COMBINATOR(200, 2, 'p') fails due to an overflow - without need. You could replace this:
prod(1:M) / (prod(1:(M-K))) => prod(M-k+1:M)
in the calculation of BC and BC1 in perms_no_rep.
Similar in combs_rep: prod(M:(M+K-1)) / prod(1:K) is more susceptible for overflows than: prod((M:(M+K-1)) ./ (1:K)). Then COMBINATOR can handle large N as long as K is small enough.
I've implemented a lot of algorithms for permutations and combinations, e.g. Knuth's. My impression: COMBINATOR is very fast and memory efficient and I do not expect, that a Matlab implementation can be faster! Even a C-MEX for COMBINATOR(N,K,'p') with comparable speed is a hard work. Unfortunately I've rated this file already - so just: thanks again.

08 Jan 2010 Matt Fig

Thanks, Jan. I will look into your suggestions and, if my findings match yours, will offer an update. I appreciate the speedup!

07 Jan 2010 Jan Simon

Efficient, compact, clear, comprehensive help and comments in the source, comparisons with other functions from the FEX.

Small improvement: In perms_loop the term "[i*ones(m,1) t]" is slower then assigning [i] and [t] separately. I simplified the computation of indices (just some % faster). Then the loop becomes:
for n = 2:M
q = P;
m = G(n-1);
P = zeros(n*m, n, CN);
P(1:m, 1) = n;
P(1:m, 2:n) = q;

a = m + 1;
for i = n-1:-1:1,
t = q;
t(t == i) = n;
b = a + m - 1;
P(a:b, 1) = i;
P(a:b, 2:n) = t;
a = b + 1;
end
end
For Matlab 7.8, this is about 30% faster than the original subroutine perms_loop. To my surprise a method with pre-allocating the complete output at once and avoiding a growing is some percent slower.

Thanks, Jan

31 Oct 2009 Matt Fig

Michele,
You didn't give very much information. If you put a number greater than 170 WHERE? And what other parameters? Why don't you just email me? I put my email in the help for that purpose. If you email me, show me EXACTLY what you did, don't be vague.

31 Oct 2009 mklcst mklcst

If I put a value greater than 170 I get an error.

25 Aug 2009 Andrey

Very good.

02 Jun 2009 Bruno Luong

Two words: excellent job!

02 Jun 2009 us

a very nice package/wrapper for a lot of the combinatorial problems almost daily asked for in the NG - or - as the name implies: a TERMINATOR for combiners...

in particular:
- excellent help/good example
- clean engine divided into intelligible subfunctions
- many comments and timings

us

Updates
16 Jun 2009

Added ability to specify integer class for N. MEX-File.

27 Jan 2010

Implemented changes suggested by Jan Simon.

09 Sep 2010

Previous update had left out the C++ source code.

Contact us