특정 위치가 변경되지 않은 문자열의 모든 순열 찾기

Question

"Ohmy"와 같이 단어의 문자열이 주어지면 대문자를 고정 (변경되지 않음) 상태로 유지하지만 소문자의 위치는 변경할 수 있습니다. 모든 가능한 순열을 출력하십시오.

예 : "OhMy"그것을해야 출력 [ "OhMy", "OyMh"] 주어진 여기

내가 무슨 짓을 : 입력

public static List<String> Permutation(String s){ 
    List<String> res = new ArrayList<String>(); 
    if (s == null || s.length() == 0){ 
     return res; 
    } 
    StringBuilder path = new StringBuilder(s); 
    List<Character> candidates = new ArrayList<Character>(); 
    List<Integer> position = new ArrayList<Integer>(); 
    for (int i = 0; i < s.length(); i++){ 
     char c = s.charAt(i); 
     if (Character.isAlphabetic(c) && Character.isLowerCase(c)){ 
      candidates.add(c); 
      position.add(i); 
     } 
    } 
    boolean[] occurred = new boolean[candidates.size()]; 
    helper(res, path, candidates, position, 0); 
    return res; 
} 

public static void helper(List<String> res, StringBuilder path, List<Character> candidates, List<Integer> position, int index){ 
    if (index == position.size()){ 
     res.add(path.toString()); 
     return ; 
    } 
    for (int i = index; i < position.size(); i++){ 
     for (int j = 0; j < candidates.size(); j++){ 
      path.setCharAt(position.get(i), candidates.get(j)); 
      char c = candidates.remove(j); 
      helper(res, path, candidates, position, index+1); 
      candidates.add(j, c); 
     } 
    } 
} 

"ABC" 이 결과를해야합니다 [ABC, ACB,도 Acc, Acb] 기본적으로 외부 루프는 가능한 모든 위치를 반복하고 내부 루프는 가능한 모든 위치에서 모든 가능한 후보를 시도합니다. 나는 왜 그것이 중복 된 "AC, Acb"를 가지고 있는지 모른다.

Answer 1

암시적인 질문의 주요 포인트는 주어진 세트의 모든 순열을 효율적으로 열거하는 방법이다. 온라인에서 읽을 수있다. 몇 가지 방법이 있습니다). 소문자 색인의 모든 순열을 열거 할 수 있다면 책 보관 및 소문자의 각 순열을 원래의 변경되지 않은 대문자 세트와 병합하여 대문자의 위치를 ​​존중하므로 매우 간단합니다. 당신은 당신의 문자열을 출력 할 수 있습니다. 그 부분에 어려움을 겪고 있다면 질문을 업데이트하면 누군가가 당신을 도울 수 있습니다.