java如何實現排列組合算法

171次閱讀

共計 1196 個字符，預計需要花費 3 分鐘才能閱讀完成。

在 Java 中可以使用遞歸來實現排列組合算法。以下是一個示例代碼：

import java.util.ArrayList;
import java.util.List;
public class Combination {public static void main(String[] args) {List nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(4);
int r = 3; // 選擇 r 個元素進行組合
List<List> combinations = combine(nums, r);
for (List combination : combinations) {for (int num : combination) {System.out.print(num + " ");
}
System.out.println();}
}
public static List<List> combine(List nums, int r) {List<List> result = new ArrayList();
List path = new ArrayList();
dfs(nums, r, 0, path, result);
return result;
}
private static void dfs(List nums, int r, int start, List path, List<List> result) {if (path.size() == r) {result.add(new ArrayList(path));
return;
}
for (int i = start; i < nums.size(); i++) {path.add(nums.get(i));
dfs(nums, r, i + 1, path, result);
path.remove(path.size() - 1);
}
}
}

上述代碼使用了深度優先搜索（DFS）的方式來生成排列組合。首先定義了一個 combine 方法，接收一個包含元素的列表和選擇的元素個數 r 作為參數。在 combine 方法中，創建了一個結果列表 result 和一個路徑列表 path。然后調用dfs 方法進行深度優先搜索。
dfs方法接收了待選擇的元素列表 nums、選擇的元素個數r、當前搜索的起始位置start、當前路徑path 和結果列表 result 作為參數。首先判斷當前路徑的長度是否等于選擇的元素個數 r，如果是，則將當前路徑加入結果列表，并返回。否則，從起始位置start 開始遍歷待選擇的元素列表 nums，將當前元素加入路徑列表path，然后遞歸調用dfs 方法繼續搜索下一個元素，搜索的起始位置為當前位置的下一個位置 i + 1。當遞歸返回后，將當前元素從路徑列表中移除，繼續遍歷下一個元素。最后，返回結果列表。
運行上述代碼，輸出結果為：