중복이없는 문자열의 순열

Question

문자열의 모든 순열을 생성하는 문제에 대한 해결책을 읽었습니다 (solution).

perm2와 perm1이 어떻게 다른지 설명 할 수 있습니까? 일부 문자는 문자열의 같은 경우

// print N! permutation of the characters of the string s (in order) 
public static void perm1(String s) { perm1("", s); } 
private static void perm1(String prefix, String s) { 
    int N = s.length(); 
    if (N == 0) System.out.println(prefix); 
    else { 
     for (int i = 0; i < N; i++) 
      perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N)); 
    } 

} 

// print N! permutation of the elements of array a (not in order) 
    public static void perm2(String s) { 
     int N = s.length(); 
     char[] a = new char[N]; 
     for (int i = 0; i < N; i++) 
      a[i] = s.charAt(i); 
     perm2(a, N); 
    } 

    private static void perm2(char[] a, int n) { 
     if (n == 1) { 
      System.out.println(a); 
      return; 
     } 
     for (int i = 0; i < n; i++) { 
      swap(a, i, n-1); 
      perm2(a, n-1); 
      swap(a, i, n-1); 
     } 
    } 

또한, 다음 몇 가지 순열이 될 것입니다 (나는 유일한 차이점은 마지막에 perm2는 동안 첫 번째 위치에 각 요소를 넣어 시도 perm1 그 느낌) 같은? 이 문제를 방지하기 위해 생각할 수있는 유일한 방법은 순열의 인스턴스를 하나만 유지하도록 결과를 해시 셋에 저장하는 것입니다. 더 나은 해결책이 있습니까?

Answer 1

두 번째 솔루션에 대한 정당성은 효율성이라고 기대합니다. String 객체가 아닌 문자 배열을 사용하고 연결을 통해 새 String을 만드는 대신 각 단계에서 문자를 서로 바꿉니다.

기능면에서 두 솔루션의 유일한 차이점은 결과가 출력되는 순서입니다.

입력에 중복 문자가있는 경우 고유 솔루션을 보장하지 않는 것이 맞습니다. 결과를 저장하고 집합을 사용하거나 직접 contains을 통해 고유성을 검사하는 것이 필요할 경우이를 피하는 가장 쉬운 방법입니다.

두 번째 해결 방법은 문자가 이미 처리되었는지 확인하는 것입니다. 결과 세트를 저장하는 오버 헤드 (긴 문자열의 경우 중요 할 수 있음)를 피할 수 있습니다. 두 번째 perm2 기능에

: (? n은 엄청난 것입니다 필요한 메모리를!,되는 순열의 수)

내가 고유성에 더있을 수 있습니다 생각

if (n == 1) { 
    System.out.println(a); 
    return; 
} 
for (int i = n; i < a.length; i++) { 
    if (a[i] == a[n-1]) 
     return; 
} 
for (int i = 0; i < n; i++) { 
    boolean duplicate = false; 
    for (int j = 0; !duplicate && j < i; j++) 
     duplicate = a[i] == a[j]; 
    if (!duplicate) { 
     swap(a, i, n-1); 
     perm2(a, n-1); 
     swap(a, i, n-1); 
    } 
}