Рубиновая анаграмма с использованием String#sum

Я решил проблему, которая требует от вас написать метод для определения того, какие слова в предоставленном массиве являются анаграммами, и сгруппировать анаграммы в подмассив в вашем выводе.

Я решил это, используя то, что кажется типичным способом, который вы бы сделали, сортируя слова и группируя их в хэш на основе их отсортированных символов.

Когда я изначально начал искать способ сделать это, я заметил, что существует String#sum, который складывает порядковые номера каждого символа вместе.

Я хотел бы попытаться разработать способ определения анаграммы на основе использования sum. Например, «автомобили» и «шрам» — это анаграммы, и их 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» равны ['cars','racs','scar']. Я думаю, что мне не хватает переноса этого в ожидаемый формат вывода.


ruby anagram
person Caley Woods    schedule 01.03.2012    source источник

Ответы (3)


arrow_upward
17
arrow_downward

К сожалению, я не думаю, что 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"]]
person Andy Lindeman    schedule 01.03.2012
comment
Кажется, это общепринятое решение, и на то есть веские причины. На первый взгляд, начиная с проблемы, я подумал, что эта сумма может показаться альтернативным способом ее решения. Мое исходное решение не такое красноречивое, как ваше, но оно использует ту же идею word.chars.sort. Просто стараюсь быть свежей :) - person Caley Woods; 01.03.2012
comment
Кроме того, я отправил свое предварительное решение, и оно прошло спецификации, которые они используют в автогрейдере, как и мое исходное решение. Я повторно отправил исходное решение, чтобы правильная реализация была в файле. Всегда интересно экспериментировать. - person Caley Woods; 01.03.2012

arrow_upward
1
arrow_downward

На самом деле, я думаю, вы могли бы использовать суммы для тестирования анаграмм, но не суммировать сами порядковые номера символов, а вместо этого что-то вроде этого:

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 — это длина самого длинного слова во входном наборе.

person Mladen Jablanović    schedule 01.03.2012
comment
Тестирование этого с использованием приведенного ниже примера zaa и yab Энди Линдеманса приводит к правильной функциональности, поскольку они не сгруппированы вместе. Я добавил вас в суть, связанную с моим комментарием Алексу Д. - person Caley Woods; 01.03.2012

arrow_upward
1
arrow_downward

Чтобы получить желаемый формат вывода, вам просто нужно hash.values. Но обратите внимание, что простое использование суммы кодов символов в слове может привести к сбою на некоторых входных данных. Суммы кодов символов в двух словах могут случайно оказаться одинаковыми, если они не являются анаграммами.

Если бы вы использовали другой алгоритм для объединения кодов символов, шансы неправильной идентификации слов как «анаграмм» могли бы быть значительно ниже, но все же не равны нулю. По сути, вам нужен какой-то алгоритм хеширования, но с тем свойством, что порядок хэшируемых значений не имеет значения. Возможно, сопоставить каждый символ с другой случайной битовой строкой и взять сумму битовых строк для каждого символа в строке?

Таким образом, вероятность того, что любые две неанаграммы дадут вам ложное срабатывание, будет примерно 2 ** bitstring_length.

person Alex D    schedule 01.03.2012
comment
В итоге я получил gist.github.com/b1fb5aab6893da0ed933. Это немного наивно, как вы упомянули, но в контексте этой головоломки я считаю, что это работает просто как еще один способ ее решить. - person Caley Woods; 01.03.2012