这里我们要处理的是把从{1,2,…,n}抽取r个数的所有组合按字典序排序,注意每个组合都保证是升序排列。问题是给定一个组合,确定其在所有组合中的序号?比如:n=4,r=2,所有组合按字典序排列如下
{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},
组合{2,4}的序号为5。一般而言,令 则可得如下递推公式:
令
因此递推公式可重新表述为
反复用这个公式可得
从而只要计算了帕斯卡矩阵,就可以快速获得任意的组合数了。
由于[n]的r子集有r个数,所以至少要做 次操作。借助于这个办法,组合数序号的计算方法的时间复杂度:加减法次数seta(r),其中seta表示与r同阶。
它可以被用在动态规划法求TSP之中,借助于它就能够实现一般参考书上所说的时间复杂度。TSP的具体实现见附录1。 附录---MATLAB代码 function [pmin,pvmin]=tspdp(D) %TSPDP 旅行销售员问题(TSP)的动态规划(Dynamic Programming)算法的递推实现 % % [pmin, pvmin] = tspdp( D ) % 输入参数:D --- 两两城市之间的距离矩阵,双精度二维数组 % 输出参数:pmin --- 最短路线双精度,一维行数组 % pvmin --- 最短距离,双精度数 % % Example: [pmin,pvmin]=tspdp(rand(5)) % % 注意:经分析,其时间复杂度为O(n*2^n),也就是说n 每增大1,运行时间大致上变成 % 原来的2 倍。因此,n不能太大,当取在12以内时,速度很快。若用C++等实现,在20以 % 内都可以接受。 n=length(D); pasmat=pascal(n+1); fP=calfP(D,pasmat); pvmin=inf; for j=1:n-1 v=fP{n-1}(j,1)+D(j,n); if pvmin>v pvmin=v; jmin=j; end end pmin=zeros(1,n+1); pmin(n:n+1)=[jmin, n]; C=1:n-1; for j=n-1:-1:1 Csn=combineseqnum(C,n-1,j,pasmat); I=find(pmin(j+1)==C); pmin(j)=fP{j}(I,2,Csn); C(I)=[]; end %------------------------------------------------------------------------ function fP=calfP(D,pasmat) n=length(D); for k=1:n-1 fP{k}=zeros(k,2,pasmat(k+1,n-k)); end for Csn=1:n-1 fP{1}(:,:,Csn)=[D(n,Csn),n]; end for k=2:n-1 C=zeros(1,k); Csn=0; curi=1; while curi if C(curi)>=n-1-k+curi curi=curi-1; else C(curi:end)=C(curi)+1:C(curi)+1+k-curi; curi=k; Csn=Csn+1; S=C(2:k); for I=1:k CI=C(I); %后面要重复使用 Ssn=combineseqnum(S,n-1,k-1,pasmat); vmin=inf; for j=1:k-1 v=fP{k-1}(j,1,Ssn)+D(S(j),CI); if vmin>v vmin=v; jmin=S(j); end end fP{k}(I,:,Csn)=[vmin, jmin]; if I<k S(I)=CI; end end end end end %----------------------------------------------------------------------- function sn=combineseqnum(p,n,r,pasmat) %COMBINESEQNUM 求{1,2,...,n}中抽取r个数构成的组合在所有组合(升序)按字典序排 % 序后所处的序号(从1开始编号)。 % % sn = combineseqnum(p , n) % 输入参数:p --- {1,2,...,n}的一个组合,用数值向量表示,行或列均可,要求按 % 升序排列 % n --- 元素的个数,即{1,2,...,n}中的 n % r --- p中元素的个数 % pasmat --- 帕斯卡矩阵 % 输出参数:sn --- p在所有组合中的按字典序排序后的编号 % % Example: sn=combineseqnum([1 3],4) % if r>1 sn=pasmat(r+1,n-r+1); for I=1:r nn=n-p(I); rr=r+1-I; if nn>=rr sn=sn-pasmat(rr+1,nn-rr+1); end end else sn=p; end |
|
来自: shuaixinerwei > 《组合数学》