반복없는 순열을위한 알고리즘? 프로그램에서

Question

내가 그 편지의 주어진 세트에 대한 아나그램을 생성하게하고, 나의 현재의 접근 방식에있다 :

1. 는 모든 문자의 모든 조합을 가져
2. 각 조합 그룹
의 순열을 받기
3. 정렬 결과 순열 순으로
4. 제거 중복 된 항목은

내 질문은 순열의 수학에 관한 것이다. 나는 평면 ​​배열을 계산하여 중복 엔트리를 제거한 후 나머지 엔트리를 저장하는 데 필요한 배열 크기를 계산할 수 있는지 궁금하다. (순열 수식과 함께 반복 문자 수를 사용).

나는 내 질문의 애매 모호함에 대해 사과하며, 나는 여전히 조합과 교체에 대해 더 연구하고있다. 조합과 순열에 대한 이해가 넓어지고 내 프로그램에 다시 익숙해지면 목표를 정교하게 다듬을 것입니다. (지난 여름의 여가 시간 프로젝트였습니다). 당신이 n 요소, 한 요소의 a[0] 중복, 다른 요소의 a[1] 중복 등 a[k]까지있는 경우

Answer 1

후 (중복까지) 별개의 순열의 총 수는 n!/(a[0]! a[1]! ... a[k]!)입니다.

참고하면 Guava으로, 관심이 있다면, 당신은

Collection<List<Character>> uniquePermutations = 
    Collections2.orderedPermutations(Lists.charactersOf(string)); 

를 작성할 수 결과는 중복 모든 것을 차지하고, 문자의 독특한 순열 될 것이다. .size() 메서드를 호출하거나 힌트를 구현하기 만하면됩니다. (공개 : 구아바에 기고합니다.)

Answer 2

모든 순열을 생성하는 것은 정말 나쁜 생각입니다. 예를 들어 단어 "오버플로"는 40320 개의 순열을가집니다. 따라서 단어 길이가 늘어남에 따라 메모리 사용량이 매우 높습니다.

해결하려는 문제는 한 단어가 다른 단어의 아나그램인지 파악하는 데 도움이 될 수 있다고 생각합니다.

그러면 각 글자가 몇 번이나 나오는지 (26- 튜플이 될 것임)를 계산하고 이러한 터플을 서로 비교하여 문제를 해결할 수 있습니다.