Ruby Anagram String # sum

Question

제공된 배열에서 어나그램이 무엇인지 확인하고 그 결과를 출력 내의 하위 배열로 그룹화하는 방법을 작성하도록 요청하는 문제를 해결했습니다.

단어를 정렬하고 정렬 된 문자를 기반으로 해시로 그룹화하는 것이 일반적인 방법 인 것처럼 보이는 방법을 사용하여 해결했습니다.

처음에이 작업을 수행하기 시작했을 때 각 문자의 서수를 함께 추가하는 String#sum이 있음을 발견했습니다.

sum을 사용하여 분석기를 결정하는 방법을 알아 보려고합니다. 예를 들어 "자동차"와 "상처"에 대한 아나그램하고 자신의 sum (나는 이미 해시 솔루션을 사용하여 얻을 수) %w[cars scar for four creams scream racs] 예상되는 출력의 입력 주어진 425

입니다 : [[cars, scar, racs],[for],[four],[creams,scream]]. '당신에게 상처를 키 "425"의 값이 ['자동차 ','RACS '는 해시를 제공하는,

input.each_with_object(Hash.new []) do |word, hash| 
    hash[word.sum] += [word] 
end 

갈 방법입니다 :

이 같은 일을 것 같아 ']. 내가 잃어버린 것 같아요 출력 예상 된 형식으로 이동합니다.

Answer 1

불행히도 String#sum이이 문제를 해결할 강력한 방법이라고 생각하지 않습니다.

고려 :

"zaa".sum # => 316 
"yab".sum # => 316 

동일 합 있지만 철자 바꾸기를.

대신 문자 정렬 순서로 그룹화하는 것이 어떻습니까? 사실

words = %w[cars scar for four creams scream racs] 

anagrams = words.group_by { |word| word.chars.sort }.values 
# => [["cars", "scar", "racs"], ["for"], ["four"], ["creams", "scream"]] 

Answer 2

원하는 출력 형식을 얻으려면 hash.values이 필요합니다. 그러나 단어의 문자 코드 합계를 사용하면 일부 입력에 실패 할 수 있습니다. 두 단어로 된 문자 코드의 합계가 anagrams가 아닌 경우 우연히 동일 할 수 있습니다.

다른 알고리즘을 사용하여 문자 코드를 결합한 경우 단어를 "분석기"로 잘못 식별 할 가능성은 훨씬 낮지 만 여전히 0이 아닙니다. 기본적으로 어떤 종류의 해시 알고리즘이 필요하지만, 속성 값이 인 값이 해시되는 것은 중요하지 않습니다. 아마도 각 문자를 다른 임의의 비트 문자열에 매핑하고 문자열의 각 문자에 대해 비트 문자열의 합계를 취합니까?

그런 식으로 거짓 포지티브를주는 두 개의 비 아나그램이 발생할 확률은 대략 2 ** bitstring_length입니다.

Answer 3

words = %w[cars scar for four creams scream racs] 
res={} 

words.each do |word| 
    key=word.split('').sort.join 
    res[key] ||= [] 
    res[key] << word 
end 

p res.values 


[["cars", "scar", "racs"], ["for"], ["four"],["creams", "scream"]] 

Answer 4

, 난 당신이 철자 바꾸기 테스트에 대한 금액을 사용하지만 문자 '서수 스스로를 합산 없습니다 생각하지만, 대신에이 같은 일이 :

words = %w[cars scar for four creams scream racs] 
# get the length of the longest word: 
maxlen = words.map(&:length).max 
# => 6 
words.group_by{|word| 
    word.bytes.map{|b| 
    maxlen ** (b-'a'.ord) 
    }.inject(:+) 
} 
# => {118486616113189=>["cars", "scar", "racs"], 17005023616608=>["for"], 3673163463679584=>["four"], 118488792896821=>["creams", "scream"]} 

확실하지 않음이 100 인 경우 %의 올바른,하지만 논리가 서 있다고 생각합니다.

아이디어는 모든 단어를 N 기반 숫자로 매핑하는 것입니다. 모든 숫자 위치는 다른 문자를 나타냅니다.N은 입력 집합에서 가장 긴 단어의 길이입니다.