使用字符串的Ruby Anagram＃sum

我解決了一個問題，要求您編寫一個方法來確定提供的數組中的單詞是anagrams，並將anagrams分組到輸出內的子數組中。使用字符串的Ruby Anagram＃sum

我已經解決了它使用什麼似乎是典型的方式，你會通過排序單詞，並根據他們的排序字符分組成一個哈希。

當我最初開始尋找一種方法來做到這一點，我注意到String#sum存在，它將每個字符的序號加在一起。

我想嘗試一些方法來確定基於使用sum的anagram。例如，「汽車」和「傷痕」是字謎及其sum是425

給出%w[cars scar for four creams scream racs]預期輸出（我已經得到使用散列溶液）的輸入是：[[cars, scar, racs],[for],[four],[creams,scream]]。

好像做這樣的事情：

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

是要走的路，這給你一個散列結果，其中的關鍵「425」中的數值[「汽車」，「RACS」，「疤痕「]。我想我錯過的是將其轉換爲輸出的預期格式。

來源

2012-03-01 Caley Woods

不幸的是，我不認爲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"]]

來源

2012-03-01 14:40:27

這似乎是普遍接受的解決方案，並有充分的理由。乍一看，當我開始解決這個問題時，我認爲這個總和似乎也許是另一種攻擊方式。我原來的解決方案不如你的雄辯，但它使用相同的word.chars.sort想法。只是想保持新鮮:) – 2012-03-01 14:56:32

此外，我也提交了我的解決方案，並通過了他們在autograder中使用的規格，就像我原來的解決方案一樣。我重新提交了原始解決方案，以便正確的實施文件。試驗總是很有趣的。 – 2012-03-01 14:58:21

要獲得所需的輸出格式，您只需要hash.values。但請注意，僅在某個字中使用字符代碼的總和可能會導致某些輸入失敗。當兩個詞中的字符代碼的總和不相同時，它們可能是偶然的。

如果您使用了不同的算法來組合字符代碼，那麼錯誤地將單詞識別爲「anagrams」的機率可能會低得多，但仍然不爲零。基本上你需要某種散列算法，但是具有散列值的order並不重要。也許將每個字符映射到一個不同的隨機比特字符串，並獲取字符串中每個字符的比特串的總和？

這樣，任何兩個非anagrams給你一個假陽性的機會大約是2 ** bitstring_length。

來源

2012-03-01 14:24:09

我結束了https://gist.github.com/b1fb5aab6893da0ed933。你提到的有點天真，但在這個難題中，我相信它只是另一種解決方法。 – 2012-03-01 14:39:16

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"]]

來源

2012-03-01 15:00:13

事實上，我認爲你可以使用字謎測試款項，但字符序不總結自己，但這樣的事情，而不是：

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是輸入集中最長單詞的長度。

來源

2012-03-01 16:43:05

使用下面的zaa和yab的Andy Lindemans示例進行測試會得到正確的功能，它們不會分組在一起。我將你的評論添加到了鏈接到Alex D. – 2012-03-01 18:05:34

使用字符串的Ruby Anagram＃sum

回答

相關問題