当前页面位置: » 丰搜网 » 文档中心 » 详细内容
一个实现排列和组合的javabean
出自：www.linuxaid.com.cn
在我们编程时，经常要涉及到排列和组合的问题。那么在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个对象的所有排列的可能。事实上，我们先生成这样的组合，然后对每一个组合进行全排列就可以了，有兴趣的读者可以自己试着实现这种功能
