C++實現(xiàn)生成組合算法

C++實現(xiàn)生成組合算法學(xué)號:姓名:TOC\o"1-5"\h\z\o"CurrentDocument"組合的基本概念 1\o"CurrentDocument"生成組合的需求 1\o"CurrentDocument"2.1生成全部組合 2\o"CurrentDocument"2.1.1基于2字典的生成全部組合算法流程 2\o"CurrentDocument"2.1.2C++代碼 2\o"CurrentDocument"2.1.3運行結(jié)果 5\o"CurrentDocument"2.2生成r-組合 6\o"CurrentDocument"2.2.1基于字典序序的r-組合算法流程 6\o"CurrentDocument"2.2.2C++代碼 6\o"CurrentDocument"2.2.3運行結(jié)果 9組合的基本概念1） 集合S={1,2,......n},所有元素組成一組的集合（不考慮排列的順序），稱為S的全部組合；2） 集合S={1,2, n}，從中選出r個元素組成一組（不考慮排列的順序），稱為S的一個r-組合。生成組合的需求Main字典序生成算法全部組合遞歸算法基于2字典序生產(chǎn)算法 Even算法Main字典序生成算法全部組合遞歸算法基于2字典序生產(chǎn)算法 Even算法生成組合包括：全部組合和r-組合。全部組合的算法有，基于2

的字典序，Even算法，遞歸算法；r-組合的算法有字典序生成算法。

2.1生成全部組合2.1.1基于2字典的生成全部組合算法流程十進制nCreate轉(zhuǎn)換為2進制，使用棧存儲。輸入集合S：初始化nMax>=從棧中輸出數(shù)據(jù)；即一個組合2.1.2C++代碼#include<iostream>#include<math.h>#include<afxtempl.h>usingnamespacestd;typedefCArray<char,char&>BinaryData;voidGetBinaryData(unsignedintnData,BinaryData&nBinaryArry,intnSize)(nBinaryArry.RemoveAll();if(0==nData)(return;unsignedintnRes=0;charnMod=0;intnPos=0;while(1!=nData)(nMod=nData%2;nData/=2;nBinaryArry.Add(nMod);nPos++;}if(1==nData)(charnTemp=1;nBinaryArry.Add(nTemp);}intn1=nBinaryArry.GetSize();if(n1<nSize)(for(intj=0;j<nSize-n1;j++)(charnTemp=0;nBinaryArry.Add(nTemp);}}//Debug//intnSize=nBinaryArry.GetSize();//for(inti=nSize-1;i>=0;i--)// (//printf("%d",nBinaryArry.GetAt(i));// }}int_tmain(intargc,TCHAR*argv[],TCHAR*envp[])(intnRetCode=0;//initializeMFCandprintanderroronfailureif(!AfxWinInit(::GetModuleHandle(NULL),NULL,::GetCommandLine(),0))(//TODO:changeerrorcodetosuityourneedscerr<<_T("FatalError:MFCinitializationfailed")<<endl;nRetCode=1;}else(BinaryDatanBinaryData;〃輸ANunsignedintN=0;printf("請輸AN:\n");cin>>N;unsignedintnCreate=0;〃計算n位個的值unsignedintnMax=0;for(unsignedinti=0;i<N;i++)(nMax+=pow(2,i);}//2字典序輸出while(nMax>=nCreate)(GetBinaryData(nCreate,nBinaryData,N);intnSize=nBinaryData.GetSize();for(intj=0;j<nSize;j++)(intnTemp=nBinaryData.GetAt(j);if(1==nTemp)(printf("%d",j+1);}}nCreate++;nBinaryData.RemoveAll();printf("\n");}}returnnRetCode;2.1.3運行結(jié)果1)3的全部組合2)4的全部組合生成下一個r-生成下一個r-組合2.2生成r-組合2.2.1基于字典序序的r-組合算法流程算法流程如下圖所示：V

組合集合數(shù)：n

；求解組合數(shù)：V計算第一個r-組合和最后一個r-組合B 7當前r-組合=第

一個r-組合AA==B'Ndo/返回當前r-組合可以加1的位置p和該位置的值v；do/算生成下一個r-組合需要更改的位置數(shù)t=r-p；do/計算下一個r-組合nMax=v+1+r-p；do/從位置r到位置t填入nMax到v+1。輸出一個r-組

合2.2.2C++代碼intmain()(R_Combination(6,4);return0;}//求解r-組合voidR_Combination(intn,intr)(

//初始化int*pBuff=newint[n];for(inti=0;i<n;i++)(pBuff[i]=i+1;}//第一個r-組合int*pFirst=newint[r];〃最后一個r-組合int*pLast=newint[r];for(intj=0;j<r;j++)(pFirst[j]=j+1;pLast[j]=n-r+j+1;//pLast[j]=j;}//debugprintf(-第一個%d-組合：\n”,r);for(inta=0;a<r;a++)(printf("%d”,pFirst[a]);}printf("\n");TRACE(-最后一個%d-組合:",r);for(intb=0;b<r;b++)(TRACE("%d”,pLast[b]);}TRACE("\n");intk=0;intp=0;while(!CompareEqual(pFirst,pLast,r))(GetMaxPosion(pFirst,r,n,&k,&p);intnMax=k+1+r-p;for(intnFill=r-1;nFill>=p-1;nFill--)(pFirst[nFill]=nMax;nMax--;for(inta=0;a<r;a++)(printf("%d”,pFirst[a]);}printf("\n");}〃釋放內(nèi)存if(NULL!=pLast)(delete[]pLast;}if(NULL!=pFirst)(delete[]pFirst;}if(NULL!=pBuff)(delete[]pBuff;}}〃比較數(shù)組內(nèi)容是否相等boolCompareEqual(int*pData1,int*pData2,intnSize)(boolbRes=true;intnV1=0;intnV2=0;for(inti=0;i<nSize;i++)(nV1=*(pData1+i);nV2=*(pData2+i);if(nV1!=nV2)(bRes=false;i=nSize+1;}}returnbRes;}voidGetMaxPosion(int*pData/*一個r-組合的指針*/,intr/*r--組合大小*/,intn/*求解的組合大小*/,int*pK/*允許加一的值*/,int*pPosition/*r-組合的位置*/)intnValue_K=0;intnValue_R=r;intnPosion=0;intnValue=0;for(inti=0;i<nValue_R;i++)(nValue=pData[i];if(nValue>nValue_K&&(nValue+1)<=n&&!IsExit(pData,r,nValue+1))(nPosion=i+1;nValue_K=*(pData+i);}}〃賦值返回*pK=nValue_K;*pPosition=nPosion;TRACE("K值