我需要生成(我更喜欢 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
在此先感谢您的帮助。
最佳答案
非常粗糙(极其无效)的解决方案。 FOR cycle over 2^nvec-1 (nvec = r*maxw) 测试样本和变量res的存储真的很糟糕!!!
此解决方案基于以下 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
关于matlab - 特定元组的生成和计数(matlab),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15518196/