Решатель анаграмм Ruby

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

Список слов такой:

the
these
one
owner

Я бы позволил пользователю вводить некоторые буквы, например noe, и он искал бы в списке слов слова, которые он может составить, используя введенные пользователем буквы, и возвращал бы one, и если бы они ввели «eth» или даже «the» это вернет the. Я пытался придумать эффективный способ сделать это, но я зацикливался на каждом слове, сопоставлял букву в слове, проверял слово для каждой буквы, и обе длины совпадают. Может ли кто-нибудь дать совет о лучшем и более эффективном способе сделать это?


ruby search algorithm anagram
person RailsSon    schedule 23.08.2011    source источник

Ответы (6)


arrow_upward
35
arrow_downward

Основная идея заключается в том, что все анаграммы идентичны при сортировке. Итак, если вы создадите хеш (не знаю, как Ruby их называет) списков, где ключи — это отсортированные слова, а значение — это список слов, которые сортируются по заданному ключу, то вы можете очень быстро найти анаграммы, отсортировав слово и искать в вашем хеше.

person Rob Neuhaus    schedule 23.08.2011
comment
Отличная идея. Как насчет решателя анаграмм из нескольких слов? Нравится rrenaud =› Ad Rerun? - person Kimmo Lehto; 24.08.2011
comment
@KimmoLehto разбить предложения на массивы, а затем удалить все экземпляры пробела из массивов. После этого отсортируйте массивы, а затем сопоставьте их. - person Ashishkumar Pandey; 23.04.2017
comment
@AshishPandey Не совсем понятно, что вы имеете в виду. Когда вы говорите разделить предложения, нет словаря всех возможных предложений. Если вы имеете в виду разбить входное предложение, и вы хотите разбить на пробелы, то вы просто находите анаграммы для входных слов, не меняя местами буквы между словами. Это не даст результата очень часто. - person Adamantish; 11.09.2019
comment
@Adamantish Будет словарь, в вопросе говорится, что есть список слов. Это словарь. Итак, предположим, что пользователь вводит teehs, разделение и отсортированный массив этого ввода будут [ 'e', 'e', 'h', 's', 't' ]. программа также будет иметь другой многомерный хеш, где ключами будут слова в словаре, а значениями будут их разделенные и отсортированные массивы. Затем мы можем просто перебрать значения хеша и получить соответствующий ключ. Надеюсь, это имеет смысл. - person Ashishkumar Pandey; 12.09.2019
comment
@AshishPandey Если вы попробуете, у вас возникнут проблемы. Во-первых, да, отсортированные массивы в порядке, но они должны быть ключами, потому что для каждого из них может быть несколько слов. И вот как вы получите производительность O (1) для слов, которые просматриваются напрямую. Но это полезно только для получения анаграммы из одного слова. Вам нужно найти все слова, содержащие ваши входные буквы, а не точное совпадение, которое дает хэш (структура данных trie в stackoverflow.com/a/1924561/2772719 лучше всего подходит для этого), тогда вы должны повторить поиск с оставшимися буквами. - person Adamantish; 12.09.2019
comment
@Adamantish, конечно, это была минутная рекомендация, а не ответ. Ваш упомянутый ответ имеет большой смысл, хотя реализовать его с первой попытки было бы сложно, и поэтому я рекомендую. - person Ashishkumar Pandey; 12.09.2019

arrow_upward
11
arrow_downward

Ответ rrenaud великолепен, и вот пример того, как построить такой хеш в ruby, учитывая массив с именем «words», который содержит все слова в вашем словаре:

@words_hash = words.each_with_object(Hash.new []) do |word, hash|
  hash[word.chars.sort] += [word]
end

В приведенном выше коде предполагается ruby ​​1.9.2. Если вы используете более старую версию, то chars не будет, но вы можете использовать .split('').sort.

Объектом хэша по умолчанию является пустой массив, что в некоторых случаях упрощает кодирование, потому что вам не нужно беспокоиться о том, что хэш даст вам ноль.

Источник: https://github.com/DavidEGrayson/anagram/blob/master/david.rb

person David Grayson    schedule 23.08.2011
comment
Это идентично words.group_by {|word| word.chars.sort } - person Jörg W Mittag; 24.08.2011
comment
Круто, но на самом деле вам нужно сделать это: @words_hash = words.group_by {|word| word.chars.sort}; @words_hash.default = [] - person David Grayson; 26.08.2011

arrow_upward
5
arrow_downward

Одним из решений может быть:

def combine_anagrams(words)
  output_array = Array.new(0)
  words.each do |w1|
    temp_array = []
    words.each do |w2|
      if (w2.downcase.split(//).sort == w1.downcase.split(//).sort)
        temp_array.push(w2)
      end
    end
    output_array.push(temp_array)
  end
  return output_array.uniq
end
person Иван Бишевац    schedule 07.03.2012

arrow_upward
3
arrow_downward

Я не мог удержаться от решения этой рубиновой викторины :)

class String

  def permutation(&block)
    arr = split(//)
    arr.permutation { |i| yield i.join }
  end
end


wordlist = ["one", "two"]

"noe".permutation do |i|
  puts "match found: #{i}" if wordlist.include?(i)
end

Основная идея заключается в том, что он создает массив и использует функцию перестановки для получения результата. Это может быть неэффективно, но я нахожу это элегантным. :D

person Rontologist    schedule 23.08.2011
comment
о боже, просто обожаю! - person thelastinuit; 30.08.2017

arrow_upward
1
arrow_downward

Это может быть то, что вы ищете: Решение анаграмм в Руби

Вот еще один подход (это лучший ответ): Решатель анаграмм в Python

person Dan W    schedule 23.08.2011

arrow_upward
1
arrow_downward

Вот очень похожий на мой. Чтение из файла словаря и сравнение отсортированных символов в виде массива. Сортировка производится по предварительно отобранным кандидатам.

def anagrams(n)
  text = File.open('dict.txt').read

  candidates = []
  text.each_line do |line|
    if (line.length - 1) == n.length
      candidates << line.gsub("\n",'')
    end
  end

  result = []

  candidates.each do |word|
    if word.chars.sort == n.chars.sort
      result << word
    end
  end

  result

end
person Kamil Sarna    schedule 09.12.2013