整数分拆是把待分拆的整数分拆成若干个小于或等于该整数的整数的和。它是堆垒数论中的研究内容。在不考虑排列顺序的情况下，例如：

      1：  1

      2：  1+1；2  

      3：  1+1+1；1+2；3

      4：  1+1+1+1；1+1+2；1+3；2+2；4

       ……

对于3有3种分拆方式，称3的分拆数为3；那么4的分拆数是5；5的分拆数是7；6的分拆数是11；7的分拆数是15；分拆数有着奇怪的规律，素数5、7等，存在以某公差的无穷整数数列，它们的分拆数可以被5、7等整除，或者被其幂整除如25、125、49、343等。据说，分拆数的公式已经在今年初被发现，并且找到了一些怪异的规律。

    姑且，不论这些分拆数的公式如何，规律如何。整数分拆的结果，即拆分的方法也是很有意思的，寻找规律编写代码让计算机去列出分拆方式以及分拆数。

若是产生1:n的整数，计算机自己去找合适的组合，那么整数稍大，很快就让我原先定下的几个组合规律一团混乱，有点不太现实。之后，琢磨了个方法，它不是以n为基础直接得到分拆方式，而是由1、2、3…逐步堆到n来分拆。

以下是它的MATLAB代码：

function result=psn(n)

s={1};

if (n==1)

    s={1};

else

    for p=1:n-1

        k=size(s,2);

        w={};

        for i=1:k

            w{i}=[1,s{i}];

        end

        t=k;

        for i=1:k

            if size(s{i},2)==1

                t=t+1;

                w{t}=s{i}+1;

            else

                if s{i}(1)+1<=s{i}(2)    

                    t=t+1;

                    w{t}=s{i};

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

                end

            end

        end

        s=w;

    end

end

    result=s;

end

元胞result的dim就是分拆数，每个胞里的数组表示一种分拆。

结果如下：

result=psn(5)

result =

 [1 1 1 1 1]  [1 1 1 2]  [1 1 3]  [1 2 2]  [1 4]  [2 3]   5

共7个元胞，即分拆数为7。

result=psn(24);

size(result,2)

ans =

   1575

——“24”的分拆数为1575。

result=psn(37);

size(result,2)

ans =

   21637

——“37”的分拆数为21637。

算法是通过“n”的拆分来实现“n+1”的拆分。三个步骤：对所有“n”的拆分的每个数组的第1项补1，其余各项右移1位做为新的拆分数组；若“n”的拆分数组项数等于1，则该数组项数不变，其值加1，做为新的拆分数组；若项数大于1，且第二项大于第一项，则第一项加1，其余项不变，做为新的数组。而初始1的拆分为{1}。

算法首先保证了数组序列的左项总是小于等于右项，对所有“n”的拆分都加个“1”产生新的拆分序列，若是某项等于它的右项则忽略，直道其右项大于它时该项便加“1”得到新的拆分序列。如此可以保证所有的“n+1”拆分项都没有遗漏，然而这样“n+1”的分拆有重复，例如，1 2 2 4至左向右1<2则有新的数组序列 2 2 2 4，2<4 则新的数组序列有 1 2 3 4，而2 3 4 第一项补“1”有1 2 3 4 ；这与补“1”的重复，在至左向右的查找时忽略所有以1做为起始项的序列，可以避免与补“1”重复，它是不会造成遗漏的，因为，必有某项补“1”后同被忽略的项产生相同的“n+1”拆分序列。此外在至左向右查找这个过程中，如 a b c与(a-1) (b+1) c这样的项也会造成“n+1”新序列的重复，皆可以得到a (b+1) c。那么，忽略序列项数大于1，且某项的左项小于等等于它的项，因为对于任意大于1的a、b总有a-1、b+1与其重复（等于1的情况先前已考虑）逐步忽略，例如：2 3 5 6与2 2 6 6会产生新的2 3 6 6；再看2 2 6 6 与 1 3 6 6 可以看到最后只要第1项，第2项的关系就可以判断是否采用该数组产生新的序列2 3 6 6所以数组序列的左项总是小于等于右项的原则保证了选择序列数组生成新序列数组时，只要选择第一项小于第二项即可避免重复、也可以避免遗漏。

************************************************************************************

上文的代码效率很糟，姑且留着，做了些修改，以下代码效率会好些。

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


转载本文请联系原作者获取授权，同时请注明本文来自黄川科学网博客。
链接地址：https://blog.sciencenet.cn/blog-567861-445323.html

上一篇：椭圆拟合及坐标扶正
下一篇：色彩空间笔记