문자열의 순열의 총 수를 찾기

Question

나는 다음과 같은 프로그램으로 지정된 캐릭터 라인의 순열의 총 수를 계산하기 위해 노력하고 있습니다 :

프로그램

class Test{ 

    public static void main(String[] args){ 
     String str = "ABC"; 
     int n = str.length(); 

     //System.out.println(permute(str, 0, n-1)); 
     permute(str, 0, n-1); 
    } 

    private static int permute(String str, int l, int r){ 
     ArrayList<String> list=new ArrayList<String>(); 
     if (l == r) 
      //System.out.println(str); 
      list.add(str); 
     else 
     { 
      for (int i = l; i <= r; i++) 
      { 
       str = swap(str,l,i); 
       permute(str, l+1, r); 
       str = swap(str,l,i); 
      } 
     } 
     /*for (int i=0;i<list.size() ;i++) { 
      System.out.println(list.get(i)); 
     }*/ 
     return list.size(); 
    } 
public static String swap(String a, int i, int j){ 
     char temp; 
     char[] charArray = a.toCharArray(); 
     temp = charArray[i] ; 
     charArray[i] = charArray[j]; 
     charArray[j] = temp; 
     return String.valueOf(charArray); 
    } 
} 

출력 : 0

다시 주어진 문자열의 순열을 표시하는 데 같은 방법을 적용합니다. 다음 프로그램은 나의 접근 방식을 보여줍니다

프로그램을

class Test{ 

    public static void main(String[] args){ 
     String str = "ABC"; 
     int n = str.length(); 

     //System.out.println(permute(str, 0, n-1)); 
     permute(str, 0, n-1); 
    } 

    private static void permute(String str, int l, int r){ 
     ArrayList<String> list=new ArrayList<String>(); 
     if (l == r) 
      //System.out.println(str); 
      list.add(str); 
     else 
     { 
      for (int i = l; i <= r; i++) 
      { 
       str = swap(str,l,i); 
       permute(str, l+1, r); 
       str = swap(str,l,i); 
      } 
     } 
     for (int i=0;i<list.size() ;i++) { 
      System.out.println(list.get(i)); 
     } 
     //return list.size(); 
    } 
public static String swap(String a, int i, int j){ 
     char temp; 
     char[] charArray = a.toCharArray(); 
     temp = charArray[i] ; 
     charArray[i] = charArray[j]; 
     charArray[j] = temp; 
     return String.valueOf(charArray); 
    } 
} 

출력 :

ABC 
ACB 
BAC 
BCA 
CBA 
CAB 

내가 0를 얻을 arraylist의 크기를 반환 할 때 내 의심의 여지가 여기에있다 출력물은 list의 모든 요소를 ​​출력 할 때 모든 순열을 표시합니다.

내 의심을 없앨 수 있습니까?

Answer 1

메서드 내에 목록을 만드는 것이 정확하지 않습니다. 재귀 때문에 최종적으로 빈 목록을 얻게됩니다. 귀하의 방법에 ArrayList을 전달할 수있는 가장 빠른 해결책. 이 같은

private static int permute(String str, int l, int r, ArrayList<String> list){ 

    if (l == r) { 
     list.add(str); 
    } 
    else { 
     for (int i = l; i <= r; i++) { 
      str = swap(str,l,i); 
      permute(str, l+1, r, list); 
      str = swap(str,l,i); 
     } 
    } 
    return list.size(); 
} 

과 전화 :

String str = "ABC"; 
    int n = str.length(); 
    ArrayList<String> list = new ArrayList<>(); 
    permute(str, 0, n-1, list); 

    System.out.println(list.size()); 

이제 출력 6해야한다.

편집

그냥 순열의 수, n이 문자열의 길이입니다 물론이 n!이있어 필요합니다. 문자열의 chars가 반복되는 경우, 다른 공식 n!/ (k1!*k2!*k3!...)하여 수행

int i = numberOfPermutations("abc".length()); 

System.out.println(i); 

UPDATE 제안으로

:

private static long numberOfPermutations(long n) { 
    if(n == 1 || n == 0) return 1; 

    return (n) * numberOfPermutations(n-1); 
} 

은이 방법을 사용합니다. Implimentation :

String string = "ABBCCCD"; 
String[] split = string.split(""); 

Map<String, Long> collect = Arrays.stream(split).collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 


long result = numberOfPermutations(string.length())/collect.values().stream().map(Main::numberOfPermutations).reduce(1L, (a, b) -> a *b); 
System.out.println(result);