File Exchange

image thumbnail

COMBINATOR -combinations AND permutations

version 1.3 (32.7 KB) by

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

41 Downloads

Updated

View License

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.

Comments and Ratings (42)

Nikhil Prabhu

Gebe

Gebe (view profile)

Solved this issue: Just replace line 343 with
BC = round(prod(M-K+1:M) / (prod(1:K)),0);
Seems to be a numerical problem.

Gebe

Gebe (view profile)

Have the same problem as mohammad: i.e. a = combinator(24,19,'c') generates a matrix with a zero row at the end...Help would be very nice!

Yi Mao

Yi Mao (view profile)

pankaj singh

VERY COOL CODE AND VERY HELPFUL IN STATISTICAL AND OTHER ENGINEERING APPLICATIONS....THANKS A LOT....

John BG

John BG (view profile)

Hi,

I have repeatedly used your function combinator.m and recommend it as often as possible because it's really useful.

However, I need to go through all permutations of a simplified alphabet set
['a' 'b' .. 'y' 'z'] 26 characters

when I try

combinator(26,26,'p')

the following error shows up:

Error using zeros
Requested 479001600x12 (42.8GB) array exceeds maximum array size preference.
Creation of arrays greater than this limit may take a long time and cause
MATLAB to become unresponsive. See array size limit or preference panel for
more information.
Error in combinator>perms_loop (line 259)
P = zeros(n*m,n,CN);
Error in combinator>perms_no_rep (line 185)
PN = perms_loop(N); % Call helper function.
Error in combinator (line 115)
A = perms_no_rep(N,K); % permutations

with

digits(30)
vpa(factorial(26),30)
=
403291461126605650322784256.0

Can you modify combinator.m so that it can handle 26!

Thanks in advance for time and attention
awaiting answer

John
jgb2012@sky.com

farah

farah (view profile)

Hello,
Can you tell me the time complexity please when I using the combination without repetition function? where for example I am using N =32, and all values of k from 1-32.

faster than nchoosek/choosenk etc. thank you very much

Hamid

Hamid (view profile)

papoo

papoo (view profile)

Thanks A LOT!

mohammad

please any help

mohammad

please , help me

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

Shane

Shane (view profile)

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.

Pouya Jamali

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.

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.

Loginatorist

Loginatorist (view profile)

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.

Alesya

Alesya (view profile)

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?

Mauricio

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

Peter

Peter (view profile)

Created a newsgroup profile just to add this rating!

Ejaz. S

Excellent work

is excellent, very fast!

Vitor F. C.

Excellent job, you saved my phd! :)

Vitor F. C.

7ate9

7ate9 (view profile)

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

Xavier

Xavier (view profile)

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?

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

Thanks a lot, Matt.
It does help.

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

Thanks a lot Matt!

Loginatorist

Loginatorist (view profile)

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

Jan Simon

Jan Simon (view profile)

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.

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.

Tal Shir

Tal Shir (view profile)

Just what I needed. Thanks.

Jan Simon

Jan Simon (view profile)

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.

Loginatorist

Loginatorist (view profile)

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

Jan Simon

Jan Simon (view profile)

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

Loginatorist

Loginatorist (view profile)

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.

mklcst mklcst

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

Andrey

Andrey (view profile)

Very good.

Bruno Luong

Bruno Luong (view profile)

Two words: excellent job!

us

us (view profile)

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

1.3

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

1.2

Implemented changes suggested by Jan Simon.

1.1

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

MATLAB Release
MATLAB 7.4 (R2007a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video