COMBINATOR -combinations AND permutations

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

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 submission has inspired the following:; VChooseK, VChooseKRO, VChooseKR, VChooseKO
• MATLAB release: MATLAB 7.4 (R2007a)
• Other Files: combinator.m, ; cumsumall.m, ; cumsumall.mexw32, ; license.txt

[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

[Bruno Luong]

Two words: excellent job!

[Andrey]

Very good.

[mklcst mklcst]

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

[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.

[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

[Matt Fig]

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

[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.

[Tal Shir]

Just what I needed. Thanks.