Рубиновая анаграмма с использованием строки # sum - PullRequest
Новая
       6

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

2 голосов
/ 01 марта 2012

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

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

Когда я впервые начал искать способ сделать это, я заметил, что существует 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']. Я думаю, что мне не хватает, перемещая это в ожидаемый формат вывода.

Ответы [ 4 ]

17 голосов
/ 01 марта 2012

К сожалению, я не думаю, что 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"]]
1 голос
/ 01 марта 2012

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

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

1 голос
/ 01 марта 2012 
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"]]
1 голос
/ 01 марта 2012

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

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

Таким образом, шансы любых двух неанаграмм, дающих вам ложное срабатывание, будут приблизительно1008 *.

...