moset的个人博客分享 http://blog.sciencenet.cn/u/moset 以心为绢,绘山河;以思为海,汇百流;以文为宴,会高朋。

博文

关于整数拆分的几个Matlab函数

已有 9824 次阅读 2012-6-28 23:01 |系统分类:科研笔记| 整数拆分、Matlab

“整数拆分MATLAB代码”中给出了一种列出所有拆分数组的算法。后来在解决一个统计问题时编写了些接口程序,例如:对数字45拆分,而数组中元素为整数,取值 4到13之间等。下面的这几个就是关于类似问题的接口程序。

1.   已知数字A,求其由xi[a,b]i=1..dim的拆分组合。

function H=p_l(dim_m,sum_m,Max,Min) %Max=b;Min=a;sum_m=A;dim_m=dim

if Min*dim_m>sum_m||Max*dim_m<sum_m

    H=[];

else

p=Max-Min;

n=sum_m-dim_m*Min;

s={[0,1]};

for i=2:n                   %when n>1

    k=size(s,2);

    w={};

    for j=1:k

        if (s{j}(end)<s{j}(end-1))&&(s{j}(end)<p)

            w{end+1}=s{j};

            w{end}(end)=w{end}(end)+1;

        end

        if size(s{j},2)<dim_m+1

            w{end+1}=s{j};

            w{end}(end+1)=1;

        end

    end

    if(i<=p)

    w{end+1}=[0,i];

    end

    s=w;

end

if dim_m*Min==sum_m    %(1)

    s={[0]};

end

H=ones(size(s,2),dim_m)*Min;

for i=1:size(s,2)

    H(i,1:size(s{i},2)-1)=s{i}(2:end)+Min;

end

end

end

(1)唯一的种情况,当Min*dim_m=sum_m时,程序执行后s原本应为空,但由于初始定义了s={[0,1]},将出现BUG,然而初始定义s={[0,1]}可使程序简便得多,所以在这种情况下必须强制置0来避免这种错误。

s={[0,1]}w{end+1}=[0,i],可以取消掉主循环中j<k的判断,size(s{j},2)<dim_m+1(s{j}(end)<p)用来实现拆分数组元素个数和大小的限定。

 

例如:5个数,最大为7,最小为3,其和为18的组合:

>>H=p_l(5,18,7,3)

H =

     4     4     4     3     3

     5     4     3     3     3

     6     3     3     3     3

p_l函数是“整数拆分MATLAB代码”中的psn函数扩展改写。

function s=psn(n)

s={1};

w=s;

for i=2:n                   %when n>1

    k=size(s,2);

    for j=1:k

        w{j}(end+1)=1;

        if (j<k)&&(s{j}(end)<s{j}(end-1))

            w{end+1}=s{j};

            w{end}(end)=w{end}(end)+1;

        end

    end

    w{end+1}=i;

    s=w;

end

end

 

2.    拆分数的递归形式。

f(Ab)A的所有以xi[1,b]i=123…为元素的拆分数,则f(A,b)=f(A,b-1)+f(A-b,b),也就是欧拉分割函数(证明很直观,这儿就忽略了)。若是只须求拆分数,使用分割函数会比psn函数快很多,但分割函数不能列出拆分数组。

function s=di_Euler(n,k) %n=A; k=b; 

if (n==0)||(k==0)  %2

    s=(n==0);    

elseif(n<k)

    s=di_Euler(n,n);

else

    s=di_Euler(n,k-1)+di_Euler(n-k,k);

end

end

>>re= di_Euler(18,18)

re=

   385

>> re=size(psn(18),2)

re =

   385

 

>> re=size(p_l(18,18,18,0),1)

re =

   385

2f(0,0)=1,0组合成0,有一种方式。f(0,3)由小于3的数组合成0有一种方式。f(x,0)=0,当x0时,不存在组合。

3.    已知数字A,求其由xi[a,b]i=123…的拆分组合。

function L=psnab(sum_m,Max,Min)

%Max=b;Min=a;sum_m=A;

dim_min=ceil(sum_m/Max);

dim_max=floor(sum_m/Min);

P={};

for i=dim_min:dim_max

    tmp=p_l(i,sum_m,Max,Min);

    if size(tmp,2)>0

        P{end+1}=tmp;

    end

end

L=[];

for i=1:size(P,2)

L=[L;[P{i},zeros(size(P{i},1),size(P{end},2)-size(P{i},2))]];

end

end

例:

L=psnab(13,13,5)

L =

    13     0

     7     6

     8     5  

暂时就这几个接口函数,以后遇到应用再补充。虽然应用中没发现其他的问题,但程序也许还存在BUG,而且效率也不算多好。谁有更好的方法,或者程序编写的建议,不吝赐教啊。



https://blog.sciencenet.cn/blog-567861-586909.html

上一篇:曾经的报数游戏
下一篇:遗忘了的,FFT的一个小角落
收藏 IP: 59.46.83.*| 热度|

1 曾新林

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-26 04:42

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部