Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
specific tuples generation and counting

Subject: specific tuples generation and counting

From: Michal Kvasnicka

Date: 19 Mar, 2013 15:12:11

Message: 1 of 9

I need to generate 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.
Michal

Subject: specific tuples generation and counting

From: Michal Kvasnicka

Date: 20 Mar, 2013 14:27:08

Message: 2 of 9

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!!! 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

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

tup =

     0 2 2 2 2
     1 1 2 2 2


mul =

     5
    10

Subject: specific tuples generation and counting

From: Michal Kvasnicka

Date: 20 Mar, 2013 14:43:10

Message: 3 of 9

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

Subject: specific tuples generation and counting

From: Bruno Luong

Date: 20 Mar, 2013 19:21:06

Message: 4 of 9

"Michal Kvasnicka" wrote in message <kichtu$sk1$1@newscl01ah.mathworks.com>...
> 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

Not sure how you get mul = 1. The only unique combination is 1 1 2 2 2.

function [t m v] = tupmul(n, w)
v = tmr(length(w), n, w);
t = sort(v,2);
[t I 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

% Bruno

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

end %tmr

Subject: specific tuples generation and counting

From: Michal Kvasnicka

Date: 20 Mar, 2013 20:51:06

Message: 5 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kid272$p9t$1@newscl01ah.mathworks.com>...
> "Michal Kvasnicka" wrote in message <kichtu$sk1$1@newscl01ah.mathworks.com>...
> > 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
>
> Not sure how you get mul = 1. The only unique combination is 1 1 2 2 2.
>
> function [t m v] = tupmul(n, w)
> v = tmr(length(w), n, w);
> t = sort(v,2);
> [t I 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
>
> % Bruno
>
> if nargin>=4 % add a head column
> v = [head+zeros(size(v,1),1,class(head)) v];
> end
>
> end %tmr

Bruno, yes you are right. My algorithm is wrong. Yours is far more better, but still I am not able to compute problems for n ~ 30, n <= sum(w) <= n+10, 5 <= r <= n in reasonable time. I understand that this problem is very probably NP-hard. So, is there any chance to parallelize tmr function? As I know, recursive functions are very hardly or completely impossible to parallelize. What do you think about any kind of additional speed up?

Subject: specific tuples generation and counting

From: Bruno Luong

Date: 21 Mar, 2013 07:18:05

Message: 6 of 9

Another algorithm

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

function c = tmr(n, w)
c = arrayfun(@(k) 1:k, w, 'Unif', 0);
[c{:}] = ndgrid(c{:});
p = length(w);
c = cat(p+1, c{:});
c = reshape(c, [], p);
c = c(sum(c,2)==n,:);
end %tmr

% Bruno

Subject: specific tuples generation and counting

From: Michal Kvasnicka

Date: 21 Mar, 2013 11:27:20

Message: 7 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kiec7d$m1u$1@newscl01ah.mathworks.com>...
> Another algorithm
>
> function [t m v] = tupmul(n, w)
> v = tmr(n, w);
> t = sort(v,2);
> [t I J] = unique(t,'rows');
> m = accumarray(J(:),1);
> end % tupmul
>
> function c = tmr(n, w)
> c = arrayfun(@(k) 1:k, w, 'Unif', 0);
> [c{:}] = ndgrid(c{:});
> p = length(w);
> c = cat(p+1, c{:});
> c = reshape(c, [], p);
> c = c(sum(c,2)==n,:);
> end %tmr
>
> % Bruno

This new algorithm produce wrong results:
>> [tup mul] = tupmul(8,[2 2 2 2 2])
tup =
     1 1 2 2 2
mul =
    10

But the rigth output is:
>> [tup mul] = tupmul(8,[2 2 2 2 2])
tup =
     0 2 2 2 2
     1 1 2 2 2
mul =
     5
    10

Subject: specific tuples generation and counting

From: Bruno Luong

Date: 21 Mar, 2013 11:37:19

Message: 8 of 9

Sorry the bug is in this line:

> > c = arrayfun(@(k) 1:k, w, 'Unif', 0);

c = arrayfun(@(k) 0:k, w, 'Unif', 0);

% Bruno

Subject: specific tuples generation and counting

From: Michal Kvasnicka

Date: 21 Mar, 2013 12:35:06

Message: 9 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kierdf$2v1$1@newscl01ah.mathworks.com>...
> Sorry the bug is in this line:
>
> > > c = arrayfun(@(k) 1:k, w, 'Unif', 0);
>
> c = arrayfun(@(k) 0:k, w, 'Unif', 0);
>
> % Bruno

Perfect code! Simple, clear and computationally effective.

There is only one drawback: extremely high memory requirements of cell "c" for realistic dimensions. Cell 'c' memory allocation size increase exponentially with length(w).

Would be possible to eliminate this effect via splitting of the algorithm on less memory consuming parts, which could be run independently (serially or parallel)?

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us