Anagram 색인 계산

Question

길이가 최대 25자인 문자 A-Z로 구성된 입력 문자열의 경우 입력 문자열의 모든 가능한 분석기 목록을 알파벳 순으로 정렬하여 색인을 출력합니다. 입력 문자열은 대소 문자를 구분하지 않습니다. 입력 문자를 반복 할 수 있습니다. 앱은 500ms 이내에 완료되고 1GB 미만의 메모리를 차지해야합니다.

언뜻보기에 이것은 임의 정밀도 수학 라이브러리 없이는 불가능한 것처럼 보입니다. 최악의 경우 25 개의 고유 한 문자가 입력되므로 25! 가능한 anagrams. 25! 2^64보다 큰 차수입니다. 인덱스와 문자열 사이의 관계가 직접적이지 않고 계산되어야하기 때문에 단순히 문자열을 숫자로 변환 할 수있는 방법이 없습니다.

나는 이전에 얻은 인터뷰 도전에서 비롯된 것입니다. 나는 그 (것)들을위한 해결책을 생각해 낼 수없고 참으로 좋은 해결책이다는 것을 주장했다 ...

Answer 1

낱말의 anagrams의 수를 세는 것은 낱말을 위해 주파수를 주어, 쉽다. 총 문자 수의 계승 값을 주파수의 계승 값으로 나눈 값입니다.이 숫자는 이라고도합니다.

이 사실을 사용하여 알파벳순으로 앞에 오는 접두사에 대한 아나그램의 수를 계산하여 모든 아나그램의 색인을 얻을 수 있습니다. 예를 들어, MISSISSIPPI : 편지 빈도는 I : 4, M : 1, P : 2, S : 4, 합계 11!/(4! 1! 2! 4!) = 34650 개입니다.

• I로 시작 아나그램의 수 (! 1! 2! 4! 3) 10!/IS = 12600
• MII 시작 아나그램의 수는 8!/(2! 0! 2! 4!) = 420
• MIP로 시작하는 분석기의 수는 8 개입니다./(3! 0! 1! 4!) = 280
• MISI로 시작하는 분석기의 수는 7 개입니다./2! 0! 2! 3!) =210
• MISP로 시작하는 분석기의 수는 7 개입니다!/(3! 0! 1! 3!) = 140
• MISSII로 시작하는 분석기 수는 5!/(1! 0! 2! 2 !) = 30
• MISSIP 시작 아나그램 수가 5!/(2! 0! 1! 2!) = 30
• 등이 ...

합이 최대 인 숫자 너는 색인을 얻는다. 하지만 네가 말했듯이, 최악의 경우에 25가 있기 때문에 네, 임의의 정밀도 넘버 라이브러리가 필요합니다. anagrams 및 인덱스가 64 비트 정수 범위를 벗어날 수 있습니다.

더 좋은 해결책이 있다면 아주 기분이 좋지 않습니다. 듣고 싶습니다.