特定元組生成和計數（MATLAB）

Question

我需要生成（I prefere MATLAB）所有的「獨特的」整數元組k = (k_1, k_2, ..., k_r)和 其相應的多重性，滿足兩個附加條件：

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

「獨特的」元組的裝置，它包含唯一的無序集合元素的 (k_1,k_2, ..., k_r)

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

典型問題尺寸大約爲：

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

（我希望存在任何多項式時間算法！）

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 

在這種情況下

只存在兩個 「唯一」 的元組：

(2,2,2,2,0)與多樣性5

有是具有相同元素集合的5個「相同」元組

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 

和

(2,2,2,1,1)與多重10

有10 「相同的」 元組相同的一組元素

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 

預先感謝任何幫助的。

Answer 1

這遠遠更多更好的算法，由布魯諾陳德良創建（驚人MATLAB程序員）：

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 

Answer 2

非常粗糙（非常無效）的解決方案。 FOR循環超過2^nvec-1（nvec = r * maxw）測試樣本和可變資源的存儲是非常可怕的事情！

該解決方案基於以下question。

還有沒有更有效的方法？

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 

或者相同情況下，但具有改變的限制爲前兩個位置：

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

tup = 

    1  1  2  2  2 


mul = 

    10