熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> JSP教程 >> 正文

關於各種排列組合java算法實現方法

2013-11-15 12:02:51  來源: JSP教程 

  一利用二進制狀態法求排列組合此種方法比較容易懂但是運行效率不高小數據排列組合可以使用

復制代碼 代碼如下:
import javautilArrays;

  //利用二進制算法進行全排列
//count:
//count:

  public class test {
public static void main(String[] args) {
long start=SystemcurrentTimeMillis();
count();
long end=SystemcurrentTimeMillis();
Systemoutprintln(endstart);
}
private static void count(){
int[] num=new int []{};
for(int i=;i<Mathpow( );i++){
String str=IntegertoString(i);
int sz=strlength();
for(int j=;j<sz;j++){
str=""+str;
}
char[] temp=strtoCharArray();
Arrayssort(temp);
String gl=new String(temp);
if(!glequals("")){
continue;
}
String result="";
for(int m=;m<strlength();m++){
result+=num[IntegerparseInt(strcharAt(m)+"")];
}
Systemoutprintln(result);
}
}
public static void count(){
int[] num=new int []{};
int[] ss=new int []{};
int[] temp=new int[];
while(temp[]<){
temp[templength]++;
for(int i=templength;i>;i){
if(temp[i]==){
temp[i]=;
temp[i]++;
}
}
int []tt=tempclone();
Arrayssort(tt);
if(!Arraysequals(ttss)){
continue;
}
String result="";
for(int i=;i<numlength;i++){
result+=num[temp[i]];
}
Systemoutprintln(result);

}
}
}

  
用遞歸的思想來求排列跟組合代碼量比較大

復制代碼 代碼如下:
package practice;

  import javautilArrayList;
import javautilList;

  
public class Test {

  /**
* @param args
*/
public static void main(String[] args) {
// TODO Autogenerated method stub
Object[] tmp={};
// ArrayList<Object[]> rs=RandomC(tmp);
ArrayList<Object[]> rs=cmn(tmp);
for(int i=;i<rssize();i++)
{
// Systemoutprint(i+"=");
for(int j=;j<rsget(i)length;j++)
{
Systemoutprint(rsget(i)[j]+"");
}
Systemoutprintln();

}
}

  
// 求一個數組的任意組合
static ArrayList<Object[]> RandomC(Object[] source)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(sourcelength==)
{
resultadd(source);
}
else
{
Object[] psource=new Object[sourcelength];
for(int i=;i<psourcelength;i++)
{
psource[i]=source[i];
}
result=RandomC(psource);
int len=resultsize();//fn組合的長度
resultadd((new Object[]{source[sourcelength]}));
for(int i=;i<len;i++)
{
Object[] tmp=new Object[resultget(i)length+];
for(int j=;j<tmplength;j++)
{
tmp[j]=resultget(i)[j];
}
tmp[tmplength]=source[sourcelength];
resultadd(tmp);
}

}
return result;
}

static ArrayList<Object[]> cmn(Object[] sourceint n)
{
ArrayList<Object[]> result=new ArrayList<Object[]>();
if(n==)
{
for(int i=;i<sourcelength;i++)
{
resultadd(new Object[]{source[i]});

}
}
else if(sourcelength==n)
{
resultadd(source);
}
else
{
Object[] psource=new Object[sourcelength];
for(int i=;i<psourcelength;i++)
{
psource[i]=source[i];
}
result=cmn(psourcen);
ArrayList<Object[]> tmp=cmn(psourcen);
for(int i=;i<tmpsize();i++)
{
Object[] rs=new Object[n];
for(int j=;j<n;j++)
{
rs[j]=tmpget(i)[j];
}
rs[n]=source[sourcelength];
resultadd(rs);
}
}
return result;
}

  }

  
利用動態規劃的思想求排列和組合

復制代碼 代碼如下:
package Acm;
//強大的求組合數
public class MainApp {
public static void main(String[] args) {
int[] num=new int[]{};
String str="";
//求個數的組合個數
// count(strnum);
// 求n個數的組合個數
count(strnum);
}

  private static void count(int i String str int[] num) {
if(i==numlength){
Systemoutprintln(str);
return;
}
count(i+strnum);
count(i+str+num[i]+""num);
}

  private static void count(int i String str int[] numint n) {
if(n==){
Systemoutprintln(str);
return;
}
if(i==numlength){
return;
}
count(i+str+num[i]+""numn);
count(i+strnumn);
}
}

  
下面是求排列

復制代碼 代碼如下:

  
package Acm;
//求排列求各種排列或組合後排列
import javautilArrays;
import javautilScanner; public class Demo {
private static boolean f[];
public static void main(String[] args) {
Scanner sc=new Scanner(Systemin);
int sz=scnextInt();
for(int i=;i<sz;i++){
int sum=scnextInt();
f=new boolean[sum];
Arraysfill(f true);
int[] num=new int[sum];
for(int j=;j<sum;j++){
num[j]=j+;
}
int nn=scnextInt();
String str="";
count(numstrnn);
}
}
/**
*
* @param num 表示要排列的數組
* @param str 以排列好的字符串
* @param nn 剩下需要排列的個數如果需要全排列則nn為數組長度
*/
private static void count(int[] num String str int nn) {
if(nn==){
Systemoutprintln(str);
return;
}
for(int i=;i<numlength;i++){
if(!f[i]){
continue;
}
f[i]=false;
count(numstr+num[i]nn);
f[i]=true;
}
}
}


From:http://tw.wingwit.com/Article/program/Java/JSP/201311/20148.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.