如何使用遞歸遍歷數組中所有可能的組合？

-2

我已經開始學習遞歸，當我解決練習問題時，我發現它很混亂。如何使用遞歸遍歷數組中所有可能的組合？

例如，如果我在排序順序[2,3,4,5,6,7,8,9]陣列和我想通過從第一數目2直到端數9開始d跳躍所有可能的組合進行迭代。

一些有效跳躍是（對於d = 3點的跳躍）：

2-> 3-> 5-> 9

2-> 3-> 6-> 9

2-> 3-> 7-> 9

2-> 3-> 8-> 9

2-> 4-> 5-> 9

等。

請告訴我如何處理這樣的遞歸問題。

來源

2017-08-17 user3243499

此問題迅速減少：刪除列表的兩端。現在，您只需從剩餘列表中選擇d-1元素。在長度爲n> m的列表中找到所有m元素的組合很容易被研究。你幾乎可以肯定地找到你最喜歡的語言的解決方案。

這種洞察力讓你感動嗎？

來源

2017-08-17 16:51:40 Prune

謝謝，現在解決了這個問題。遞歸可能有時會令人困惑。特別是對於像我這樣的新手來說。 – user3243499

不開玩笑。遞歸組合和置換代碼在大多數流行語言中都是可用的。你一般需要關於遞歸的註釋，在SO或整個Internet上搜索「遞歸解釋基本情況」。這應該會給你很大比例的有用命中。 – Prune

這裏是計算可能啤酒花一類的實現：

public class HopCalculator { 

    private int[] input; 

    public HopCalculator(int[] input) { 
    this.input = input; 
    }

輸入陣列中的施工時間給予。現在我們可以查詢不同長度的路由（跳數）。輸出是一個包含可能路線的集合。每個路由是一個數組列表，它包含它經過的數字。

public Set<ArrayList<Integer>> findPossibleHops(int d) { 
    Set<ArrayList<Integer>> options = new HashSet<>(); 
    ArrayList<Integer> option = new ArrayList<>(); 
    option.add(input[0]); 

    findPossibleHopsRecursive(options, option, d-1, 1, input.length-2); 
    return options; 
    } 

    private void findPossibleHopsRecursive(Set<ArrayList<Integer>> options, ArrayList<Integer> option, int d, int begin, int end) { 
    if (d==0) { 
     option.add(input[end+1]); 
     options.add(option); 
    } 
    else { 
     if (end - begin + 1 == d) { 
      option.add(input[begin]); 
      findPossibleHopsRecursive(options, option, d - 1, begin + 1, end); 
     } else { 
      ArrayList<Integer> option1 = new ArrayList<>(); 
      option1.addAll(option); 
      option1.add(input[begin]); 
      findPossibleHopsRecursive(options, option1, d - 1, begin + 1, end); 

      ArrayList<Integer> option2 = new ArrayList<>(); 
      option2.addAll(option); 
      findPossibleHopsRecursive(options, option2, d, begin + 1, end); 
     } 
    } 
    } 
}

來源

2017-08-17 19:00:11

如何使用遞歸遍歷數組中所有可能的組合？

回答

相關問題