熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

一個實現排列和組合的JavaBean

2013-11-23 19:05:35  來源: Java核心技術 

  在我們編程時經常要涉及到排列和組合的問題那麼在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個對象的所有排列的可能
From:http://tw.wingwit.com/Article/program/Java/hx/201311/26258.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.