Tìm tất cả các kết hợp trong arraylist đệ quy

Question

Tôi hoàn toàn bị mất về điều này. Tôi có thể làm điều này lặp đi lặp lại, nhưng đệ quy là mới đối với tôi. Nếu tôi đưa ra một ArrayList với 1, 2, 3 bên trong của nó, tổng combo có thể với lặp đi lặp lại là 27.

111, 112, 113, 121, 122, 123, vv ...

làm thế nào tôi có thể tìm thấy điều này đệ quy? Tôi muốn hiển thị mã của tôi nhưng tôi thậm chí không chặt chẽ để nhận được các khái niệm ...

Answer 1

Dưới đây là một giải pháp mã hóa nặng nề, em chỉ cần thực hiện trong trăn, nhưng nó phải chứng minh nguyên tắc:

def combinations(original,indexes): 
    indexes[2] = indexes[2] + 1 
    if(indexes[2] == 3): 
     indexes[1] = indexes[1] + 1 
     indexes[2] = 0 

    if(indexes[1] == 3): 
     indexes[0] = indexes[0] + 1 
     indexes[1] = 0 

    if(indexes[0] != 3): 
     print str(original[indexes[0]]) + str(original[indexes[1]]) \ 
      + str(original[indexes[2]]) 
     combinations(original, indexes) 


combinations([1,2,3],[0,0,0]) 

Lưu ý cách tôi có các kết hợp hàm(). Hàm này lấy mảng ban đầu làm tham số và mảng thứ hai để theo dõi các chỉ mục.

Khi tôi gọi chức năng để khởi động nó, tôi đã khởi tạo chỉ mục mảng thành tất cả 0s.

Tại mỗi chức năng trong ngăn xếp, bạn nên tăng chỉ mục trong mảng chỉ mục để tạo ra kết quả chính xác. Lưu ý làm thế nào trong giải pháp của tôi, tôi sử dụng ba nếu báo cáo, đây là phần cứng mã hóa. Điều này có thể được thực hiện với vòng lặp for.

Cuối cùng, hàm kết hợp() được gọi lại bên trong chính nó (đệ quy) với mảng chỉ mục sửa đổi cho đến khi mệnh đề kết thúc được đáp ứng (chỉ mục đầu tiên đã được max).

đoạn

Mã này nên đóng vai trò như một hướng dẫn viên như tôi thấy bạn gắn thẻ java

Answer 2

Đây là một phương pháp trong java:

String combine(ArrayList<Integer> a, String b){ 
String c=""; 
    if(b.length()==a.size()){ 
    System.out.println(b); //found a combo 
    return ""; 
    } 
    //append characters to string b 
    for(int x=0;x<a.size();x++){ 
    c=b+((Integer)a.get(x)).intValue(); 
    c+=combine(a,c); 
    } 
    return c; 
} 

Trong mỗi lần lặp của vòng lặp, nó sẽ nối thêm một nhân vật để chuỗi b từ arraylist a và gọi chính nó đệ quy. Khi độ dài của chuỗi b đạt đến 3 (tức là kích thước của danh sách mảng a), điều đó có nghĩa là một kết hợp được tạo và điều này được hiển thị. Phương pháp này được tổng quát hóa cho danh sách mảng của bất kỳ kích thước nào.

Answer 3

Bạn có thể sử dụng khái niệm này và thực hiện chức năng đệ quy của riêng bạn. bằng cách sử dụng mà bạn có thể nhận được tất cả các kết hợp có thể.

Answer 4

Làm thế nào về một giải pháp mà sẽ không quan tâm nếu bạn thay đổi kích thước của ArrayList?

public static void main(String args[]) { 
    ArrayList<Integer> ali = new ArrayList<>(); 
    ali.add(1); 
    ali.add(2); 
    ali.add(3); 

    System.out.println(combinations(ali).toString().replace("], [", "],\n [")); 
} 

Đây chỉ là một chút trợ giúp khi bắt đầu.

public static List<List<Integer>> combinations(List<Integer> input) { 
    return step(input, input.size(), new ArrayList<>()); 
} 

Đây là phương pháp đệ quy,

public static List<List<Integer>> step(List<Integer> input, 
             int k, 
             List<List<Integer>> result) { 

    // We're done 
    if (k == 0) { 
     return result; 
    } 

    // Start with [[1], [2], [3]] in result 
    if (result.size() == 0) { 
     for (Integer i : input) { 
      ArrayList<Integer> subList = new ArrayList<>(); 
      subList.add(i); 
      result.add(subList); 
     } 

     // Around we go again. 
     return step(input, k - 1, result); 
    } 

    // Cross result with input. Taking us to 2 entries per sub list. Then 3. Then... 
    List<List<Integer>> newResult = new ArrayList<>(); 
    for (List<Integer> subList : result) { 
     for(Integer i : input) { 
      List<Integer> newSubList = new ArrayList<>(); 
      newSubList.addAll(subList); 
      newSubList.add(i); 
      newResult.add(newSubList); 
     } 
    } 

    // Around we go again. 
    return step(input, k - 1, newResult); 
} 

Đầu ra:

[[1, 1, 1], 
[1, 1, 2], 
[1, 1, 3], 
[1, 2, 1], 
[1, 2, 2], 
[1, 2, 3], 
[1, 3, 1], 
[1, 3, 2], 
[1, 3, 3], 
[2, 1, 1], 
[2, 1, 2], 
[2, 1, 3], 
[2, 2, 1], 
[2, 2, 2], 
[2, 2, 3], 
[2, 3, 1], 
[2, 3, 2], 
[2, 3, 3], 
[3, 1, 1], 
[3, 1, 2], 
[3, 1, 3], 
[3, 2, 1], 
[3, 2, 2], 
[3, 2, 3], 
[3, 3, 1], 
[3, 3, 2], 
[3, 3, 3]] 

Answer 5

Tôi hiểu cuộc đấu tranh của mình. Giải quyết các vấn đề đệ quy thường có thể khó khăn khi nói đến việc theo dõi tất cả các cuộc gọi và quyết định cách điều hướng vấn đề. Sau một chút suy nghĩ, tôi đã có thể giải quyết vấn đề này, sử dụng một mảng int để biểu diễn hoán vị và một ArrayList để lưu trữ. Không có vòng lặp nào được sử dụng, cũng không kiểm tra lặp lại.

Tôi đã viết một phương thức dễ gọi là getPermutations cho phép bạn tìm tất cả hoán vị có độ dài n với số nguyên [1, n]. Phương thức này gọi phương thức đệ quy thực tế, phức tạp hơn một chút. Khi giải quyết một vấn đề như thế này, điều quan trọng là phải theo dõi các điểm dữ liệu nhất định bằng cách sử dụng các đối số của phương thức, tuy nhiên điều này làm cho phương pháp hơi đau đớn khi thực sự gọi (do đó sử dụng phương thức trợ giúp). Mã của tôi được hiển thị bên dưới.

//Recursive Method 
public static ArrayList<int[]> permutationsFrom(int[] start,int i, int val, ArrayList<int[]> prev) { 
    int n = start.length; 
    if (i == n) { 
     final int[] perm = start.clone(); 
     prev.add(perm); 
     return prev; 
    } 
    else if (val > n) { 
     return prev; 
    } 
    else { 
     int[] next = start.clone(); 
     next[i] = val; 
     prev.addAll(permutationsFrom(next, i+1, 1, new ArrayList<int[]>())); 
     return permutationsFrom(next, i, ++val, prev); 
    } 
} 

//Invokation 
public static ArrayList<int[]> getPermutations(int n) { 
    return permutationsFrom(new int[n], 0, 1, new ArrayList<int[]>()); 
} 

//Print the results 
public static void main(String[] args) { 
    ArrayList<int[]> perms = getPermutations(3); 
    System.out.println(perms.size()); 
    for (int[] perm : perms) { 
     for (int el : perm) { 
      System.out.print(el + " "); 
     } 
     System.out.println(); 
    } 
} 

như thế nào đệ quy hoạt động:

• bắt đầu với một hoán vị hoàn toàn "không xác định": mỗi giá trị có thể ở mọi chỉ số có thể cần phải được tìm thấy

• tại chỉ số hiện tại, i , đệ quy gọi lại phương thức để ghi lại mọi giá trị, val, từ 1 đến n

• hoán vị hoàn chỉnh đã được tìm thấy khi i == n (tức là mỗi chỉ số đã được xác định từ 0 đến n-1), và do đó các mảng int nên được bổ sung vào bộ sưu tập các hoán vị trước, prev

• nếu val> n mỗi giá trị có thể (từ 1 đến n) tại chỉ số i đã được chiếm, vì vậy bộ sưu tập có thể được trả lại (mà tại đó các điểm phương pháp này sẽ tiếp tục tăng i và di chuyển theo chiều ngang)

Answer 6

Bit muộn để bên này, & xin lỗi, đó là trong C#, nhưng này, nó tương tự như Java. Mọi thứ ở đây có vẻ hơi phức tạp, vì vậy đây là một chức năng khá đơn giản, nên dễ dàng dịch sang Java -

public static List<List<T>> Permutations<T>(List<T> list) 
    { 
     List<List<T>> result = new List<List<T>>(); 

     for (int i = 0; i < list.Count(); i++) 
     { 
      T initialValue = list[i]; 
      List<T> clonedList = list.Where((item, index) => { return index != i; }).ToList(); // proper copy, less the initialValue item 

      // here's where the recursion happens, but only if there are at least 2 items left in the list 
      List<List<T>> permutations = clonedList.Count > 0 ? Permutations(clonedList) : new List<List<T>> { new List<T>() }; 

      foreach (List<T> permutation in permutations) 
      { 
       List<T> combined = new List<T> { initialValue }; 
       combined.AddRange(permutation); 

       result.Add(combined); 
      } 
     } 

     return result; 
    }