排列與組合是算法學習中的經典題型。本文整理三種常見思路:二進制狀態法、遞歸法,以及動態規劃思想,並附上代碼,便於對比理解。
這種方法直觀易懂,但運行效率不高,適合小數據量的排列組合。
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; // 回溯
}
}
三種方法各有側重:枚舉法好懂但慢,遞歸法靈活,回溯式的排列最為通用。理解「選擇—遞推—回溯」的套路後,這類問題便能觸類旁通。