DIV CSS 佈局教程網

Java 排列組合的三種算法實現思路
編輯:關於JavaScript     

排列與組合是算法學習中的經典題型。本文整理三種常見思路:二進制狀態法、遞歸法,以及動態規劃思想,並附上代碼,便於對比理解。

一、二進制狀態法

這種方法直觀易懂,但運行效率不高,適合小數據量的排列組合。

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);
  }
  // 利用九進制枚舉,篩選出恰好包含 0~8 的排列
  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);
    }
  }
}

二、遞歸法

用遞歸求任意組合與指定個數的組合,代碼量稍大,但思路清晰。

// 求一個數組的任意組合
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;
}

// 求從 source 中取 n 個的組合
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;
}

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

利用「選或不選」的遞歸分支求組合:

// 求恰好 n 個數的組合
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);                     // 不選
}

用一個標記數組控制「用過 / 沒用過」,即可求排列:

private static boolean f[];
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