Số biến số lồng nhau cho vòng lặp

Question

Tôi đang tạo từ unscrambler trong java. Ngay bây giờ tôi có một chương trình có thể in tất cả các sắp xếp lại của 3 chữ cái được chọn từ một từ có 3 chữ cái trở lên (không lặp lại). Ví dụ: nếu tham số là abcd, nó sẽ in:

[[abc, abd, acb, acd, adb, adc, bac, bad, bca, bcd, bda, bdc, cab, cad , cba, cbd, cda, cdb, dab, dac, dba, dbc, dca, dcb]]

Tôi đang điền danh sách mảng 2D với các hoán vị. Ngay bây giờ mảng 2D chỉ có một mảng bên trong nó, chứa các hoán vị cho 3 chữ cái. Tôi muốn mảng 2D có mảng cho phép đọc 1 chữ cái, 2 chữ cái, 3 chữ cái, v.v., dừng ở độ dài của từ. Vấn đề là tôi cần một số lượng biến được lồng vào nhau để thực hiện điều này. Đối với các hoán vị 3 chữ cái, tôi có 3 lồng nhau cho các vòng lặp. Mỗi một chu kỳ thông qua các chữ cái trong tham số.

public static void printAllPermuations(String word) 
{ 
    int len = word.length(); 
    ArrayList<String> lets = new ArrayList<String>(); 
    //this array of letters allows for easier access 
    //so I don't have to keep substringing 
    for (int i = 0; i < len; i++) 
    { 
     lets.add(word.substring(i, i + 1)); 
    } 

    ArrayList<ArrayList<String>> newWords = new ArrayList<ArrayList<String>>(); 
    newWords.add(new ArrayList<String>()); 
    for (int i = 0; i < len; i++) 
    { 
     for (int j = 0; j < len; j++) 
     { 
      for (int k = 0; k < len; k++) 
      { 
       if (i != j && i != k && j != k) 
       //prevents repeats by making sure all indices are different 
       { 
        newWords.get(0).add(lets.get(i) + lets.get(j) + lets.get(k)); 
       } 
      } 
     } 
    } 
    System.out.println(newWords); 
} 

Tôi đã xem các bài đăng khác và tôi nghe nói rằng đệ quy có thể giải quyết vấn đề này. Tôi không biết làm thế nào tôi sẽ thực hiện điều đó, mặc dù. Và tôi cũng đã thấy một số giải pháp phức tạp mà tôi không hiểu. Tôi yêu cầu giải pháp đơn giản nhất, cho dù nó có liên quan đến đệ quy hay không.

Answer 1

Với phương pháp đệ quy, bạn sẽ đặt một vòng lặp của bạn trong một hàm vượt qua các tham số vòng lặp cho hàm đó. Sau đó, từ bên trong vòng lặp của hàm, nó gọi nó để lồng một vòng lặp khác.

void loopFunction(ArrayList<ArrayList<String>> newWords, int level) { 
    if (level == 0) { // terminating condition 
     if (/* compare the indices by for example passing down a list with them in */) 
     { 
      newWords.get(...).add(...); 
     } 
    } else {// inductive condition 
     for (int i = 0; i < len; i++) { 
      loopFunction(newWords, level-1); 
     } 
    } 
} 

Vì vậy, ví dụ của bạn, bạn cần 3 cấp đệ quy, do đó bạn sẽ bắt đầu đệ quy với:

loopFunction(newWords, 3); 

Sửa

Vì bạn đã gặp khó khăn ở đây là một phiên bản làm việc . Nó giữ một danh sách các chỉ mục để so sánh và nó xây dựng chuỗi như nó đi. Các từ được sắp xếp lại được thêm vào mảng 2D ở mỗi cấp để nhận được tất cả các từ. Với đệ quy nó là dễ nhất để suy nghĩ chức năng và không thay đổi và giữ cho các biến không thay đổi (không thay đổi). Mã này chủ yếu là mặc dù tôi cập nhật indices thay vì tạo một bản sao mới để thuận tiện.

void loopFunction(ArrayList<String> lets, ArrayList<ArrayList<String>> newWords, int level, ArrayList<Integer> indices, String word) { 
    if (level == 0) { // terminating condition 
     return; 
    } else { // inductive condition 
     for (int i = 0; i < lets.size(); i++) { 
      if (!indices.contains(i)) { // Make sure no index is equal 
       int nextLevel = level-1; 
       String nextWord = word+lets.get(i); 

       newWords.get(level-1).add(nextWord); 

       indices.add(i); 
       loopFunction(lets, newWords, nextLevel, indices, nextWord); 
       indices.remove((Integer) i); 
      } 
     } 
    } 
} 

Answer 2

tôi sẽ không cung cấp cho bạn mã thực tế, nhưng điều này sẽ cho bạn những ý tưởng như thế nào đệ quy có thể trông giống như (tôi tin rằng có những cách khác để làm điều đó một cách đệ quy: P)

void findAllCombination(String tmpResult, 
         String rawString, 
         int noOfChar, 
         List<String> allCombinations) { 
    if (tmpResult.size() == noOfChar) { 
    allCombinations.add(tmpResult); 
    } else { 
    for (i in 0 to rawString.size()) { 
     findAllCombination(tmpResult + rawString[i], 
         rawString.removeCharAt(i), 
         noOfChar, 
         allCombinations); 
    } 
    } 
} 

List<String> foo(String input, int level) { 
    List<String> allResults = ...; 
    findAllCombination("", input, level, allResults); 
    return allResults; 
} 

Phần đệ quy chính là findAllCombination. Ý tưởng là nghiêm ngặt về phía trước. Đối với cách để tìm tất cả hoán vị, cho đầu vào rawString mà chúng ta có, chúng ta lấy ra từng ký tự một, và nối thêm vào tmpResult đã tìm thấy trước đó, và sử dụng tmpResult đó để xử lý tiếp. Một khi chúng tôi nhấn điểm tmpResult là đủ dài, sau đó chúng tôi đặt tmpResult vào danh sách kết quả allCombinations.

(foo() phương pháp là ở đây chỉ để chắc gọi của bạn dễ dàng hơn: P Các mã mà thực sự làm các công trình là chỉ có 6 dòng, trừ dòng với chỉ dấu ngoặc và dòng bỏ qua mà tôi phá vỡ cố ý để có thể đọc tốt hơn)

Answer 3

dựa trên những gì @DrYap nói, tôi đã viết này (đó là một chút khác biệt so với mình):

đây là đoạn mã để bắt đầu nó đi:

for(int i = 1; i <= len; i++) 
{ 
    newWords.add(new ArrayList<String>()); 
    loop(i); 
} 

Dưới đây là phương pháp lặp. Rất nhiều biến được khai báo dưới dạng biến mẫu để tôi không phải chuyển chúng vào tham số:

public static void loop(int level) 
{ 
    if (level == 0) 
    { 
     int pos = indices.size() - 1; 
     int pos2 = newWords.get(pos).size(); 
     newWords.get(pos).add(""); 
     for (Integer letIndex : indices) 
     { 
      String previous = newWords.get(pos).get(pos2); 
      newWords.get(pos).set(pos2, previous + lets.get(letIndex)); 
     } 
    } 
    else 
    { 
     for (int i = 0; i < len; i++) 
     { 
      if (!indices.contains(i)) 
      { 
       int indicesIndex = indices.size(); 

       indices.add((Integer) i); 
       loop(level - 1); 
       indices.remove(indicesIndex); 
      } 
     } 
    } 
}