我正在嘗試使用遞回實作組合方法。我已經使用 for 回圈完成了它，但想通過遞回來處理它。
該方法獲取兩個輸入并創建所有可能的組合。它應該將組合存盤在我稱之為“組合”的實體變數中。我嘗試了不同的代碼，但它們不能正常作業。我認為遞回回溯是解決這個問題的最佳方法。
例如，object.pe1.combination(4,3) 會創建如下內容： 組合串列的影像
// Instance variable needed for this problem
ArrayList<Integer[]> combination;
private int size;
// To calculate all the possible combinations
private int factorial(int x){
if (x == 0) {
return 1;
}
else {
return x * factorial(x - 1);
}
}
void combination(int n, int r) {
// formula for calculating the combination of r items selected among n: n! / (r! * (n - r)!)
int noc = factorial (n) / (factorial (r) * factorial (n - r)); // number of combinations
this.combination = new ArrayList<Integer[]>(noc); // 2D array. Each slot stores a combination
if (noc == 0) {
}
else {
this.combination = new ArrayList<Integer[]>(noc);
int[] arr = new int[n];
int[] temparr = new int[r];
arr = createCombination(temparr, 0, r);
}
}
private int[] createCombination(int[] temparr, int index, int r) {
// this is where I am stuck
temparr[0] = index;
if (temparr[r] == 0) {
temparr = new int[r - 1];
temparr = createCombination(temparr, index 1, r - 1);
}
else {
return temparr;
}
}
uj5u.com熱心網友回復：
任何演算法的遞回實作都由兩部分組成：
- 基本情況- 終止遞回呼叫分支并表示結果預先知道的邊緣情況的條件；
- 遞回案例- 邏輯所在的部分并進行遞回呼叫。
對于此任務，基本情況將是組合大小等于目標大小的情況（r在您的代碼中表示，在下面的代碼中我給了它一個名稱targetSize）。
遞回邏輯的解釋：
- 每個方法呼叫都會跟蹤它自己的
combination； - 除非達到 ，否則每個組合
targetSize都用作blue-print for other combinations; - 資料源中的每個專案都可以使用
only once，因此當它被添加到組合時，它必須從源中洗掉。
ArrayList<Integer[]>您用來存盤組合的型別不是一個好的選擇。陣列和泛型不能很好地結合在一起。List<List<Integer>>將更適合此目的。
同樣在我的代碼List中用作資料源而不是陣列，這不是復雜的轉換并且可以輕松實作。
注意代碼中的注釋。
private List<List<Integer>> createCombination(List<Integer> source, List<Integer> comb, int targetSize) {
if (comb.size() == targetSize) { // base condition of the recursion
List<List<Integer>> result = new ArrayList<>();
result.add(comb);
return result;
}
List<List<Integer>> result = new ArrayList<>();
Iterator<Integer> iterator = source.iterator();
while (iterator.hasNext()) {
// taking an element from a source
Integer item = iterator.next();
iterator.remove(); // in order not to get repeated the element has to be removed
// creating a new combination using existing as a base
List<Integer> newComb = new ArrayList<>(comb);
newComb.add(item); // adding the element that was removed from the source
result.addAll(createCombination(new ArrayList<>(source), newComb, targetSize)); // adding all the combinations generated
}
return result;
}
對于輸入
createCombination(new ArrayList<>(List.of(1, 2, 3)), new ArrayList<>(), 2));
它會產生輸出
[[1, 2], [1, 3], [2, 3]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/424811.html
上一篇：試圖將數學公式翻譯成python