一個實現排列和組合的JavaBean

2019-11-18 12:05:32

字體：大中小

來源：轉載

供稿：網友

　　在我們編程時，經常要涉及到排列和組合的問題。那么在java中應該如何實現呢？其實這個問題首先是個算法的問題，明確了算法，用什么編程語言倒是顯得不那么重要了。
　　
　　一、全排列
　　所謂全排列，就是對n個對象，列出其所有可能的排列順序。這個問題相對來說要簡單一點。讓我們先從最簡單的情況著手，假如我們只有一個對象，該如何實現其全排列呢？答案很簡單，現在我們只有一種排列。OK，現著我們試著引入第二個對象，首先我們需要知道，現在增加了幾種全排列的可能，我們可以這么看，第n個對象的引入，對于n-1個對象的全排列的影響就是在原先的每一個全排列中的任一位置插入第n個對象，也就是說，listcount(n)=listcount(n-1)*n；而按照這個思路，對于任意n個對象的全排列，我們都可以從最簡單的一個對象的全排列開始直到生成全部n個對象的全排列。
　　
　　二、組合
　　所謂組合，就是從n個對象中取出任意m個對象的全部可能。這個問題可能要復雜一點。對于組合來說，對象的順序是沒有意義的，1、2、3和3、2、1是同一種可能。那么我們有必要人為地制定一個規則，我們可以設想給每一個對象編上連續的序號，而在我們的組合中對象必須是按其序號的順序排列，這樣我們就能有效地避免排列順序對我們的影響。假定我們現在有六個對象，其序號是1、2、3、4、5、6。那么我們的第一種組合是1、2、3，而最后一種組合則是4、5、6。在此之間，我們經歷了其它有可能出現的18種情況，對于這種算法我們很自然地會想到使用遞歸函數。首先我們先在我們的結果集中定義第一種可能是1、2、3，然后我們把當前位置定為最后一位，只要有可能，對于最后一位來說，它的最大值只能是6，在未到6之前，每增加一次就增加一種新的組合，假如最后一位已經是6，則我們將當前位置轉入前一位，前一位的最大值是5，假如前一位還沒到5，則將前一位加一，然后當前位置再度轉入最后一位，現在最后一位的最小值是4，從4開始直到6，又形成了我們新的組合，這樣，直到我們最終出現4、5、6這個組合時，函數退出。
　　下面是我們的Java源程序：
　　mytest.java:
　　package customers;
　　public class mytest
　　{String[] mychar=new String[50];
　　int charcount;
　　int charlist;
　　public void SetMyTest()
　　//初始化
　　{charcount=0;
　　charlist=1;
　　}
　　public void insertChar(String thischar)
　　//增加新的字符串
　　{charcount++;
　　mychar[charcount]=thischar;
　　charlist*=charcount;
　　}
　　public String listAllChar()
　　//列出全排列
　　{String[][] allchar=new String[charlist+1][charcount+1];
　　int i;
　　int j;
　　int z=1;
　　for (i=1;i<=charcount;i++)
　　{myCopy(addCharList(i,allchar,z),allchar,charlist,charcount);
　　z*=i;
　　}
　　String listallchar=new String(/"/");
　　for (i=1;i<=charlist;i++)
　　{for (j=1;j<=charcount;j++)
　　listallchar+=allchar[i][j]+/" /";
　　listallchar=listallchar+/"<BR>/";
　　}
　　return listallchar;
　　}
　　public String[][] addCharList(int i,String[][] allchar,int z)
　　//在i-1個對象的全排列中引入第i個對象
　　{int j;
　　int h=1;
　　int k;
　　String[][] tempallchar=new String[charlist+1][charcount+1];
　　for (k=1;k<=z;k++)
　　{for (j=1;j<=i;j++)
　　{myCopy(tempchar(j,allchar[k],mychar[i]),tempallchar[h],charcount);
　　h++;
　　}
　　}
　　return tempallchar;
　　}
　　public String[] tempchar(int i,String[] beginchar,String thischar)
　　//將新對象插入指定位置
　　{int j;
　　String[] tempbeginchar=new String[charcount+1];
　　myCopy(beginchar,tempbeginchar,charcount);
　　for (j=charcount;j>i;j--) tempbeginchar[j]=tempbeginchar[j-1];
　　tempbeginchar[i]=thischar;
　　return tempbeginchar;
　　}
　　public String selectSomeChar(int select)
　　//列出其中取出select個對象的全部組合
　　{int selectcount=1;
　　int i;
　　for (i=select+1;i<=charcount;i++) selectcount=selectcount*i/(i-select);
　　String[][] selectchar=new String[selectcount+1][select+1];
　　int[][] selectint=new int[selectcount+1][select+1];
　　for (i=1;i<=select;i++)
　　{selectchar[1][i]=mychar[i];
　　selectint[1][i]=i;
　　}
　　int z=1;
　　addSelect(selectchar,selectint,1,select,select);
　　int j;
　　String selectsomechar=new String(/"/");
　　for (i=1;i<=selectcount;i++)
　　{for (j=1;j<=select;j++)
　　selectsomechar+=selectchar[i][j]+/" /";
　　selectsomechar=selectsomechar+/"<BR>/";
　　}
　　return selectsomechar;
　　}
　　public void addSelect(String[][] selectchar,int[][] selectint,int z,int position,int select)
　　//增加新的組合
　　{int i;
　　if (position==select)
　　{if (selectint[z][position]<charcount)
　　{z++;
　　myCopy(selectint[z-1],selectint[z],select);
　　selectint[z][select]++;
　　for (i=1;i<=select;i++) selectchar[z][i]=mychar[selectint[z][i]];
　　addSelect(selectchar,selectint,z,position,select);
　　}
　　else
　　{position--;
　　addSelect(selectchar,selectint,z,position,select);
　　}
　　}
　　else
　　{if (selectint[z][position]<charcount-select+position)
　　{selectint[z][position]++;
　　selectint[z][position+1]=selectint[z][position]+1;
　　position++;
　　addSelect(selectchar,selectint,z,position,select);
　　}
　　else
　　{if (position==1)
　　{return;
　　}
　　else
　　{position--;
　　addSelect(selectchar,selectint,z,position,select);
　　}
　　}
　　}
　　}
　　public void myCopy(String[][] Str1,String[][] Str2,int i,int j)
　　{int h;
　　int k;
　　for (h=1;h<=i;h++) for (k=1;k<=j;k++) Str2[h][k]=Str1[h][k];
　　}
　　public void myCopy(String[] Str1,String[] Str2,int i)
　　{int h;
　　for (h=1;h<=i;h++) Str2[h]=Str1[h];
　　}
　　public void myCopy(int[] Str1,int[] Str2,int i)
　　{int h;
　　for (h=1;h<=i;h++) Str2[h]=Str1[h];
　　}
　　}
　　現在我們可以在一個jsp程序中使用這個JavaBean：
　　<%@ page contentType=/"text/Html;charset=gb2312/" %>
　　<HTML>
　　<HEAD>
　　<TITLE>
　　排列和組合
　　</TITLE>
　　</HEAD>
　　<BODY>
　　<jsp:useBean id=/"mytest/" scope=/"page/" class=/"customers.mytest/" />
　　<%
　　mytest.SetMyTest();
　　mytest.insertChar(/"YSY/");
　　mytest.insertChar(/"DBF/");
　　mytest.insertChar(/"CYY/");
　　mytest.insertChar(/"YKF/");
　　mytest.insertChar(/"SJJ/");
　　mytest.insertChar(/"YZDS/");
　　out.PRint(mytest.listAllChar());
　　out.print(mytest.selectSomeChar(3));
　　%>
　　</BODY>
　　</HTML>
　　
　　三、排列
　　所謂排列，就是從n個對象中取出m個對象的所有排列的可能。

上一篇：Rational為由設計直接生成代碼努力

下一篇：關于繼承和接口的一個非常有趣的比喻