在我们编程时经常要涉及到排列和组合的问题那么在Java中应该如何实现呢？其实这个问题首先是个算法的问题明确了算法用什么编程语言倒是显得不那么重要了
一全排列
所谓全排列就是对n个对象列出其所有可能的排列顺序这个问题相对来说要简单一点让我们先从最简单的情况着手如果我们只有一个对象该如何实现其全排列呢？答案很简单现在我们只有一种排列OK现着我们试着引入第二个对象首先我们需要知道现在增加了几种全排列的可能我们可以这么看第n个对象的引入对于n个对象的全排列的影响就是在原先的每一个全排列中的任一位置插入第n个对象也就是说listcount(n)=listcount(n)*n而按照这个思路对于任意n个对象的全排列我们都可以从最简单的一个对象的全排列开始直到生成全部n个对象的全排列
二组合
所谓组合就是从n个对象中取出任意m个对象的全部可能这个问题可能要复杂一点对于组合来说对象的顺序是没有意义的和是同一种可能那么我们有必要人为地制定一个规则我们可以设想给每一个对象编上连续的序号而在我们的组合中对象必须是按其序号的顺序排列这样我们就能有效地避免排列顺序对我们的影响假定我们现在有六个对象其序号是那么我们的第一种组合是而最后一种组合则是在此之间我们经历了其它有可能出现的种情况对于这种算法我们很自然地会想到使用递归函数首先我们先在我们的结果集中定义第一种可能是然后我们把当前位置定为最后一位只要有可能对于最后一位来说它的最大值只能是在未到之前每增加一次就增加一种新的组合如果最后一位已经是则我们将当前位置转入前一位前一位的最大值是如果前一位还没到则将前一位加一然后当前位置再度转入最后一位现在最后一位的最小值是从开始直到又形成了我们新的组合这样直到我们最终出现这个组合时函数退出
下面是我们的Java源程序
mytestjava:
package customers;
public class mytest
{String[] mychar=new String[];
int charcount;
int charlist;
public void SetMyTest()
//初始化
{charcount=;
charlist=;
}
public void insertChar(String thischar)
//增加新的字符串
{charcount++;
mychar[charcount]=thischar;
charlist*=charcount;
}
public String listAllChar()
//列出全排列
{String[][] allchar=new String[charlist+][charcount+];
int i;
int j;
int z=;
for (i=;i<=charcount;i++)
{myCopy(addCharList(iallcharz)allcharcharlistcharcount);
z*=i;
}
String listallchar=new String(\\);
for (i=;i<=charlist;i++)
{for (j=;j<=charcount;j++)
listallchar+=allchar[i][j]+\ \;
listallchar=listallchar+\<BR>\;
}
return listallchar;
}
public String[][] addCharList(int iString[][] allcharint z)
//在i个对象的全排列中引入第i个对象
{int j;
int h=;
int k;
String[][] tempallchar=new String[charlist+][charcount+];
for (k=;k<=z;k++)
{for (j=;j<=i;j++)
{myCopy(tempchar(jallchar[k]mychar[i])tempallchar[h]charcount);
h++;
}
}
return tempallchar;
}
public String[] tempchar(int iString[] begincharString thischar)
//将新对象插入指定位置
{int j;
String[] tempbeginchar=new String[charcount+];
myCopy(beginchartempbegincharcharcount);
for (j=charcount;j>i;j) tempbeginchar[j]=tempbeginchar[j];
tempbeginchar[i]=thischar;
return tempbeginchar;
}
public String selectSomeChar(int select)
//列出其中取出select个对象的全部组合
{int selectcount=;
int i;
for (i=select+;i<=charcount;i++) selectcount=selectcount*i/(iselect);
String[][] selectchar=new String[selectcount+][select+];
int[][] selectint=new int[selectcount+][select+];
for (i=;i<=select;i++)
{selectchar[][i]=mychar[i];
selectint[][i]=i;
}
int z=;
addSelect(selectcharselectintselectselect);
int j;
String selectsomechar=new String(\\);
for (i=;i<=selectcount;i++)
{for (j=;j<=select;j++)
selectsomechar+=selectchar[i][j]+\ \;
selectsomechar=selectsomechar+\<BR>\;
}
return selectsomechar;
}
public void addSelect(String[][] selectcharint[][] selectintint zint positionint select)
//增加新的组合
{int i;
if (position==select)
{if (selectint[z][position]<charcount)
{z++;
myCopy(selectint[z]selectint[z]select);
selectint[z][select]++;
for (i=;i<=select;i++) selectchar[z][i]=mychar[selectint[z][i]];
addSelect(selectcharselectintzpositionselect);
}
else
{position;
addSelect(selectcharselectintzpositionselect);
}
}
else
{if (selectint[z][position]<charcountselect+position)
{selectint[z][position]++;
selectint[z][position+]=selectint[z][position]+;
position++;
addSelect(selectcharselectintzpositionselect);
}
else
{if (position==)
{return;
}
else
{position;
addSelect(selectcharselectintzpositionselect);
}
}
}
}
public void myCopy(String[][] StrString[][] Strint iint j)
{int h;
int k;
for (h=;h<=i;h++) for (k=;k<=j;k++) Str[h][k]=Str[h][k];
}
public void myCopy(String[] StrString[] Strint i)
{int h;
for (h=;h<=i;h++) Str[h]=Str[h];
}
public void myCopy(int[] Strint[] Strint i)
{int h;
for (h=;h<=i;h++) Str[h]=Str[h];
}
}
现在我们可以在一个JSP程序中使用这个JavaBean
<%@ page contentType=\text/html;charset=gb\ %>
<HTML>
<HEAD>
<TITLE>
排列和组合
</TITLE>
</HEAD>
<BODY>
<jsp:useBean id=\mytest\ scope=\page\ class=\customersmytest\ />
<%
mytestSetMyTest();
mytestinsertChar(\YSY\);
mytestinsertChar(\DBF\);
mytestinsertChar(\CYY\);
mytestinsertChar(\YKF\);
mytestinsertChar(\SJJ\);
mytestinsertChar(\YZDS\);
outprint(mytestlistAllChar());
outprint(mytestselectSomeChar());
%>
</BODY>
</HTML>
三排列
所谓排列就是从n个对象中取出m个对象的所有排列的可能
