specific tuples generation and counting (matlab)

Question

I need to generate (I prefere MATLAB) all "unique" integer tuples k = (k_1, k_2, ..., k_r) and its corresponding multiplicities, satisfying two additional conditions:

1. sum(k) = n
2. 0<=k_i<=w_i, where vector w = (w_1,w_2, ..., w_r) contains predefined limits w_i.

"Unique" tuples means, that it contains unique unordered set of elements (k_1,k_2, ..., k_r)

[t,m] = func(n,w)
t ... matrix of tuples, m .. vector of tuples multiplicities

Typical problem dimensions are about:

n ~ 30, n <= sum(w) <= n+10, 5 <= r <= n

(I hope that exist any polynomial time algorithm!!!)

 Example:

n = 8, w = (2,2,2,2,2), r = length(w) 

[t,m] = func(n,w)

t = 

2 2 2 2 0 

2 2 2 1 1

m = 

5

10

in this case exist only two "unique" tuples:

(2,2,2,2,0) with multiplicity 5

there are 5 "identical" tuples with same set of elements

 0     2     2     2     2

 2     0     2     2     2

 2     2     0     2     2

 2     2     2     0     2

 2     2     2     2     0

and

(2,2,2,1,1) with multiplicity 10

there are 10 "identical" tuples with same set of elements

 1     1     2     2     2

 1     2     1     2     2

 1     2     2     1     2

 1     2     2     2     1

 2     1     1     2     2

 2     1     2     1     2

 2     1     2     2     1

 2     2     1     1     2

 2     2     1     2     1

 2     2     2     1     1

Thanks in advance for any help.

score 1 · Answer 1 · edited May 23 '17 at 10:25

1

Very rough (extremely ineffective) solution. FOR cycle over 2^nvec-1 (nvec = r*maxw) test samples and storage of variable res are really terrible things!!!

This solution is based on tho following question.

Is there any more effective way?

function [tup,mul] = tupmul(n,w)
r = length(w);
maxw = max(w);
w = repmat(w,1,maxw+1);
vec = 0:maxw;
vec = repmat(vec',1,r);
vec = reshape(vec',1,r*(maxw+1));
nvec = length(vec);
res = [];
for i = 1:(2^nvec - 1)
    ndx = dec2bin(i,nvec) == '1';
    if sum(vec(ndx)) == n && all(vec(ndx)<=w(ndx)) && length(vec(ndx))==r
        res = [res; vec(ndx)];
    end
end
tup = unique(res,'rows');
ntup = size(tup,1);
mul = zeros(ntup,1);
for i=1:ntup
    mul(i) = size(unique(perms(tup(i,:)),'rows'),1);
end
end

Example:

> [tup mul] = tupmul(8,[2 2 2 2 2])

tup =

     0 2 2 2 2
     1 1 2 2 2


mul =

     5
    10

Or same case but with changed limits for first two positions:

>> [tup mul] = tupmul(8,[1 1 2 2 2])

tup =

     1     1     2     2     2


mul =

    10

edited May 23 '17 at 10:25

Community

1
1

answered Mar 20 '13 at 14:36

michal

239
2
9

So apparently my `unique` / `perms` approach did help you after all? :-) – Eitan T Mar 20 '13 at 15:27
Yes! But multiplicities can be computed more effectively ... see next answer – michal Mar 20 '13 at 19:13
[tup mul] = tupmul(8,[1 1 2 2 2]) produce wrong result, should be mul = 1 – michal Mar 20 '13 at 20:04
Yes ... bitter grapes of truth :) – michal Mar 20 '13 at 20:57

michal · Accepted Answer · 2013-03-20T21:23:48.603

This is far more better algorithm, created by Bruno Luong (phenomenal MATLAB programmer):

function [t, m, v] = tupmul(n, w)
v = tmr(length(w), n, w);
t = sort(v,2);
[t,~,J] = unique(t,'rows');
m = accumarray(J(:),1);
end % tupmul

function v = tmr(p, n, w, head)
if p==1
    if n <= w(end)
        v = n;
    else
        v = zeros(0,1);
    end
else
    jmax = min(n,w(end-p+1));
    v = cell2mat(arrayfun(@(j) tmr(p-1, n-j, w, j), (0:jmax)', ...
        'UniformOutput', false));
end

if nargin>=4 % add a head column
    v = [head+zeros(size(v,1),1,class(head)) v];
end

end %tmr

specific tuples generation and counting (matlab)

2 Answers2