DIV CSS 佈局教程網

Java 排列組合算法大全:二進制、遞歸與動態規劃三種思路
編輯:JavaScript綜合知識     

排列與組合是演算法學習中的經典題型。本文整理三類常見思路,分別示範如何在 Java 中實作,並比較它們的特性與適用情境。

一、二進制狀態法

這種方法比較好懂,但運行效率不高,適合小數據量的排列組合:

import java.util.Arrays;

public class test {
  public static void main(String[] args) {
    long start=System.currentTimeMillis();
    count2();
    long end=System.currentTimeMillis();
    System.out.println(end-start);
  }
  private static void count2(){
    int[] num=new int []{1,2,3,4,5,6,7,8,9};
    for(int i=1;i<Math.pow(9, 9);i++){
      String str=Integer.toString(i,9);
      int sz=str.length();
      for(int j=0;j<9-sz;j++){
        str="0"+str;
      }
      char[] temp=str.toCharArray();
      Arrays.sort(temp);
      String gl=new String(temp);
      if(!gl.equals("012345678")){
        continue;
      }
      String result="";
      for(int m=0;m<str.length();m++){
        result+=num[Integer.parseInt(str.charAt(m)+"")];
      }
      System.out.println(result);
    }
  }
  public static void count1(){
    int[] num=new int []{1,2,3,4,5,6,7,8,9};
    int[] ss=new int []{0,1,2,3,4,5,6,7,8};
    int[] temp=new int[9];
    while(temp[0]<9){
      temp[temp.length-1]++;
      for(int i=temp.length-1;i>0;i--){
        if(temp[i]==9){
          temp[i]=0;
          temp[i-1]++;
        }
      }
      int []tt=temp.clone();
      Arrays.sort(tt);
      if(!Arrays.equals(tt,ss)){
        continue;
      }
      String result="";
      for(int i=0;i<num.length;i++){
        result+=num[temp[i]];
      }
      System.out.println(result);
    }
  }
}

二、遞歸思想求排列與組合

用遞歸來求解,程式碼量較大,但邏輯優雅:

package practice;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
  public static void main(String[] args) {
    Object[] tmp={1,2,3,4,5,6};
    ArrayList<Object[]> rs=cmn(tmp,3);
    for(int i=0;i<rs.size();i++)
    {
      for(int j=0;j<rs.get(i).length;j++)
      {
        System.out.print(rs.get(i)[j]+",");
      }
      System.out.println();
    }
  }

  // 求一個數組的任意組合
  static ArrayList<Object[]> RandomC(Object[] source)
  {
    ArrayList<Object[]> result=new ArrayList<Object[]>();
    if(source.length==1)
    {
      result.add(source);
    }
    else
    {
      Object[] psource=new Object[source.length-1];
      for(int i=0;i<psource.length;i++)
      {
        psource[i]=source[i];
      }
      result=RandomC(psource);
      int len=result.size();
      result.add((new Object[]{source[source.length-1]}));
      for(int i=0;i<len;i++)
      {
        Object[] tmp=new Object[result.get(i).length+1];
        for(int j=0;j<tmp.length-1;j++)
        {
          tmp[j]=result.get(i)[j];
        }
        tmp[tmp.length-1]=source[source.length-1];
        result.add(tmp);
      }
    }
    return result;
  }

  static ArrayList<Object[]> cmn(Object[] source,int n)
  {
    ArrayList<Object[]> result=new ArrayList<Object[]>();
    if(n==1)
    {
      for(int i=0;i<source.length;i++)
      {
        result.add(new Object[]{source[i]});
      }
    }
    else if(source.length==n)
    {
      result.add(source);
    }
    else
    {
      Object[] psource=new Object[source.length-1];
      for(int i=0;i<psource.length;i++)
      {
        psource[i]=source[i];
      }
      result=cmn(psource,n);
      ArrayList<Object[]> tmp=cmn(psource,n-1);
      for(int i=0;i<tmp.size();i++)
      {
        Object[] rs=new Object[n];
        for(int j=0;j<n-1;j++)
        {
          rs[j]=tmp.get(i)[j];
        }
        rs[n-1]=source[source.length-1];
        result.add(rs);
      }
    }
    return result;
  }
}

三、動態規劃思想求排列與組合

以下示範求組合數的強大寫法:

package Acm;

public class MainApp {
  public static void main(String[] args) {
    int[] num=new int[]{1,2,3,4,5};
    String str="";
    // 求 3 個數的組合個數
    // count(0,str,num,3);
    // 求 1-n 個數的組合個數
    count1(0,str,num);
  }

  private static void count1(int i, String str, int[] num) {
    if(i==num.length){
      System.out.println(str);
      return;
    }
    count1(i+1,str,num);
    count1(i+1,str+num[i]+",",num);
  }

  private static void count(int i, String str, int[] num,int n) {
    if(n==0){
      System.out.println(str);
      return;
    }
    if(i==num.length){
      return;
    }
    count(i+1,str+num[i]+",",num,n-1);
    count(i+1,str,num,n);
  }
}

再來看求排列的寫法:

package Acm;

import java.util.Arrays;
import java.util.Scanner;

public class Demo19 {
  private static boolean f[];
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int sz=sc.nextInt();
    for(int i=0;i<sz;i++){
      int sum=sc.nextInt();
      f=new boolean[sum];
      Arrays.fill(f, true);
      int[] num=new int[sum];
      for(int j=0;j<sum;j++){
        num[j]=j+1;
      }
      int nn=sc.nextInt();
      String str="";
      count(num,str,nn);
    }
  }
  /**
   * @param num 表示要排列的數組
   * @param str 已排列好的字符串
   * @param nn 剩下需要排列的個數,若需全排列則 nn 為數組長度
   */
  private static void count(int[] num, String str, int nn) {
    if(nn==0){
      System.out.println(str);
      return;
    }
    for(int i=0;i<num.length;i++){
      if(!f[i]){
        continue;
      }
      f[i]=false;
      count(num,str+num[i],nn-1);
      f[i]=true;
    }
  }
}

三種思路各有千秋:二進制法直觀但效率偏低,適合小規模;遞歸法結構清晰、易於擴展;而帶有回溯與狀態標記的排列寫法則在處理較大數據時更為高效。可依實際需求挑選合適的實作。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved