중첩 된 루프의 수 가변

Question

java에서 단어 해독기를 만들고 있습니다. 지금 나는 3 개 이상의 글자 (반복 없음)가있는 단어에서 선택된 3 글자의 모든 재 배열을 인쇄 할 수있는 프로그램을 가지고있다.

[[abc 방송, ABD, ACB, ACD, ADB, ADC, 혈중 알코올 농도, 나쁜, BCA, BCD, BDA, BDC, 택시, CAD : 매개 변수가 ABCD 경우에 따라서, 예를 들어,이 인쇄됩니다 , cba, cbd, cda, cdb, dab, dac, dba, dbc, dca, dcb]]

순열로 2D 배열 목록을 채울 것입니다. 현재 2D 배열에는 3 개의 문자에 대한 순열이 들어있는 배열이 하나만 있습니다. 2 차원 배열은 1 문자, 2 문자, 3 문자 등의 순열을위한 배열을 가지고 단어의 길이에서 멈추고 싶습니다. 문제는이 작업을 수행하기 위해 여러 개의 중첩 된 루프가 필요하다는 것입니다. 3 글자 순열의 경우, 3 중첩 된 for 루프가 있습니다. 각각은 매개 변수의 문자를 순환합니다.

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); 
} 

다른 게시물을 살펴본 결과 재귀가이를 해결할 수 있다고 들었습니다. 하지만 어떻게 구현할지 모르겠습니다. 그리고 내가 이해하지 못하는 몇 가지 복잡한 해결책을 보았습니다. 재귀가 포함되는지 여부와 관계없이 가장 간단한 해결 방법은 입니다.

Answer 1

재귀 적 방법을 사용하면 루프 매개 변수를 해당 함수에 전달하는 함수에 루프를 넣을 수 있습니다. 그런 다음 함수의 루프 내에서 다른 루프가 중첩되도록 호출합니다.

loopFunction(newWords, 3); 

편집

여기에서 문제가되고 있기 때문에이 작업 버전입니다 : 당신이 재귀를 시작할 것 때문에

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); 
     } 
    } 
} 

은 그래서 예를 들어, 당신은 재귀의 3 단계가 필요합니다 . 비교할 인덱스 목록을 유지하고 문자열이 올라갈 때마다 문자열을 만듭니다. 재 배열 된 단어는 각 레벨에서 2D 배열에 추가되어 모든 단어 길이를 얻습니다. 재귀를 사용하면 함수 적으로 생각하고 변수를 변경하지 않고 변수를 변경하지 않는 (변경 불가능한) 상태로 유지하는 것이 가장 쉽습니다. 이 코드는 대부분 편의상 새 복사본을 만들지 않고 indices을 업데이트하지만 대부분 수행합니다.

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

내가 당신에게 실제 코드를 제공하지 않습니다, 그러나 이것은 당신에게 재귀 (I 재귀 적으로 그것을 할 다른 방법이 있습니다 생각 : 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; 
} 

을 주요 재귀 부분은 findAllCombination입니다. 아이디어는 엄격한 전진이다. 모든 순열을 찾는 방법은 우리가 가지고있는 rawString 입력에 대해 문자 하나 하나를 꺼내어 이전에 찾은 tmpResult에 추가하고 그 처리를 위해 그 tmpResult를 사용합니다. 일단 tmpResult가 충분히 길다면 tmpResult를 결과 allCombinations list에 넣습니다.

Answer 3

:

(실제로 작품을 P 코드가 더 나은 가독성을 위해 의도적으로 파괴에만 브래킷과 무시 라인 라인을 제외한 만 6 라인입니다 foo는() 메소드는 사용자의 호출을 쉽게하기 위해 여기에있다) @DrYap 말한 바탕으로, 나는이 (가 자신보다 약간 다르다) 작성 :

여기

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

는 루프 방법 : 여기

그것을 시작하는 코드이다. 많은 변수가 인스턴스 변수로 선언되었으므로 매개 변수로 전달할 필요가 없습니다.

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); 
      } 
     } 
    } 
}