Impossible de combiner les mots anglais de lettres par Ruby

Question

Je dois trouver tous les mots anglais qui peuvent être formés à partir des lettres dans une chaîne

sentence="Ziegler's Giant Bar" 

Je peux faire un tableau de lettres par

sentence.split(//) 

Comment puis-je faire plus de 4500 mots anglais à partir de la phrase dans Ruby?

[modifier]

Il peut être préférable de diviser le problème en plusieurs parties:

1. pour faire seulement un tableau de mots avec 10 lettres ou moins
2. les mots plus longs peuvent être regardé up séparément

Answer 1

[En supposant que vous pouvez réutiliser la source lettres dans un mot]: Pour chaque mot de votre liste de dictionnaire, construisez deux tableaux de lettres - un pour le mot candidat et un pour la chaîne d'entrée. Soustrayez le tableau de lettres d'entrée du mot tableau de lettres et s'il n'y avait plus de lettres, vous avez une correspondance. Code à faire qui ressemble à ceci:

def findWordsWithReplacement(sentence) 
    out=[] 
    splitArray=sentence.downcase.split(//) 
    `cat /usr/share/dict/words`.each{|word| 
     if (word.strip!.downcase.split(//) - splitArray).empty? 
      out.push word 
     end 
    } 
    return out 
end 

Vous pouvez appeler cette fonction à partir du débogueur RIR comme ceci:

output=findWordsWithReplacement("some input string"); puts output.join(" ") 

... ou est ici une enveloppe que vous pouvez utiliser pour appeler la fonction interactive de un script:

puts "enter the text." 
ARGF.each {|line| 
    puts "working..." 
    out=findWordsWithReplacement(line) 
    puts out.join(" ") 
    puts "there were #{out.size} words." 
} 

Lors de l'exécution de cette sur un Mac, la sortie ressemble à ceci:

$./findwords.rb
entrez le texte.
Giant Bar de Ziegler
travail ...
A a aa AAL aalii Aani Ab aba abaiser abalienate Abantes Abaris abas abase abaser Abasgi abasie Abassin abatable Abate abater abatis abaze Abba abb abbas Abbasi Abbassi Abbatial abbesse Abbie Abe Abear Abel abele Abelia abélien Abelite abelite abeltree Aberia aberrate aberrante ABET abettal Abie Abies abietate abietene abietin Abietineae Abiezer Abigail Abigail abigeat abilla
ab intestat[....]
Z z za Zabaean zabeta Zabian Zabra zabti zabtie zag zain Zan Zanella zant zante Zanzalian Zanze Zanzibari ZAR zaratite zareba zat Zati Zattare Zea zèle zealless zeallessness zèbre-zèbre Zebrina zebrine zee zéine zeist zel Zelanian Zeltinger Zen Zenaga zenana zer zeste zêta ziara ziarat zibeline civette ziega Zieger zig zigzag zigzagger Zilla zing zingel Zingiber zingiberene Zinnia de Zinzar Zira zirai Zirbanit Zirian Zirianian Zizania Zizia zizz
il y avait 6725 mots.

C'est bien plus de 4500 mots, mais c'est parce que le dictionnaire de mots Mac est assez grand. Si vous voulez reproduire exactement les résultats de Knuth, téléchargez et décompressez le dictionnaire de Knuth à partir d'ici: http://www.packetstormsecurity.org/Crackers/wordlists/dictionaries/knuth_words.gz et remplacez "/ usr/share/dict/words" par le chemin vers l'emplacement où vous avez décompressé le répertoire de remplacement. Si vous l'avez bien vous aurez 4514 mots, finissant dans cette collection:

Zanier Zanies loufoquerie Zanzibar zazen zèbres zébrées zèle Zeiss Zeitgeist zeste Zen Zennist zestier zeta Ziegler zig zigging zigzags en zigzag en zigzag zing zingier zings zinnia

Je crois que cela répond à la question originale.

Alternativement, le questionneur/lecteur aurait pu vouloir lister tous les mots que l'on peut construire à partir d'une chaîne sans en réutilisant l'une des lettres d'entrée. Mon code suggéré pour accomplir cela fonctionne comme suit: Copier le mot candidat, puis pour chaque lettre dans la chaîne d'entrée, supprimer de façon destructive la première instance de cette lettre de la copie (en utilisant "tranche!"). Si ce processus absorbe toutes les lettres, acceptez ce mot.

def findWordsNoReplacement(sentence) 
    out=[] 
    splitInput=sentence.downcase.split(//) 
    `cat /usr/share/dict/words`.each{|word| 
     copy=word.strip!.downcase 
     splitInput.each {|o| copy.slice!(o) } 
     out.push word if copy=="" 
    } 
    return out 
end 

Answer 2

Je ne pense pas que Ruby ait un dictionnaire anglais. Mais vous pouvez essayer de stocker toutes les permutations de la chaîne d'origine dans un tableau, et vérifier ces chaînes contre Google? Dire qu'un mot est en fait un mot, s'il a plus de 100.000 hits ou quelque chose?

Answer 3

Vous pouvez obtenir un tableau de lettres comme ceci:

sentence = "Ziegler's Giant Bar" 
letters = sentence.split(//) 

Answer 4

Si vous voulez trouver les mots dont ceux-ci sont limités par l'expression donnée lettres et fréquence, vous pouvez construire une regex pour le faire pour vous :

sentence = "Ziegler's Giant Bar" 

# count how many times each letter occurs in the 
# sentence (ignoring case, and removing non-letters) 
counts = Hash.new(0) 
sentence.downcase.gsub(/[^a-z]/,'').split(//).each do |letter| 
    counts[letter] += 1 
end 
letters = counts.keys.join 
length = counts.values.inject { |a,b| a + b } 

# construct a regex that matches upto that many occurences 
# of only those letters, ignoring non-letters 
# (in a positive look ahead) 
length_regex = /(?=^(?:[^a-z]*[#{letters}]){1,#{length}}[^a-z]*$)/i 
# construct regexes that matches each letter up to its 
# proper frequency (in a positive look ahead) 
count_regexes = counts.map do |letter, count| 
    /(?=^(?:[^#{letter}]*#{letter}){0,#{count}}[^#{letter}]*$)/i 
end 

# combine the regexes, to form a regex that will only 
# match words that are made of a subset of the letters in the string 
regex = /#{length_regex}#{count_regexes.join('')}/ 

# open a big file of words, and find all the ones that match 
words = File.open("/usr/share/dict/words") do |f| 
    f.map { |word| word.chomp }.find_all { |word| regex =~ word } 
end 

words.length #=> 3182 
words #=> ["A", "a", "aa", "aal", "aalii", "Aani", "Ab", "aba", "abaiser", "Abantes", 
      "Abaris", "abas", "abase", "abaser", "Abasgi", "abate", "abater", "abatis", 
      ... 
      "ba", "baa", "Baal", "baal", "Baalist", "Baalite", "Baalize", "baar", "bae", 
      "Baeria", "baetzner", "bag", "baga", "bagani", "bagatine", "bagel", "bagganet", 
      ... 
      "eager", "eagle", "eaglet", "eagre", "ean", "ear", "earing", "earl", "earlet", 
      "earn", "earner", "earnest", "earring", "eartab", "ease", "easel", "easer", 
      ... 
      "gab", "Gabe", "gabi", "gable", "gablet", "Gabriel", "Gael", "gaen", "gaet", 
      "gag", "gagate", "gage", "gageable", "gagee", "gageite", "gager", "Gaia", 
      ... 
      "Iberian", "Iberis", "iberite", "ibis", "Ibsenite", "ie", "Ierne", "Igara", 
      "Igbira", "ignatia", "ignite", "igniter", "Ila", "ilesite", "ilia", "Ilian", 
      ... 
      "laang", "lab", "Laban", "labia", "labiate", "labis", "labra", "labret", "laet", 
      "laeti", "lag", "lagan", "lagen", "lagena", "lager", "laggar", "laggen", 
      ... 
      "Nabal", "Nabalite", "nabla", "nable", "nabs", "nae", "naegate", "naegates", 
      "nael", "nag", "Naga", "naga", "Nagari", "nagger", "naggle", "nagster", "Naias", 
      ... 
      "Rab", "rab", "rabat", "rabatine", "Rabi", "rabies", "rabinet", "rag", "raga", 
      "rage", "rager", "raggee", "ragger", "raggil", "raggle", "raging", "raglan", 
      ... 
      "sa", "saa", "Saan", "sab", "Saba", "Sabal", "Saban", "sabe", "saber", 
      "saberleg", "Sabia", "Sabian", "Sabina", "sabina", "Sabine", "sabine", "Sabir", 
      ... 
      "tabes", "Tabira", "tabla", "table", "tabler", "tables", "tabling", "Tabriz", 
      "tae", "tael", "taen", "taenia", "taenial", "tag", "Tagabilis", "Tagal", 
      ... 
      "zest", "zeta", "ziara", "ziarat", "zibeline", "zibet", "ziega", "zieger", 
      "zig", "zing", "zingel", "Zingiber", "zira", "zirai", "Zirbanit", "Zirian"] 

lookaheads positives vous permettent de faire une expression régulière qui correspond à une position dans la chaîne où un certain modèle spécifié correspond sans consommer la partie de la chaîne qui correspond. Nous les utilisons ici pour faire correspondre la même chaîne à plusieurs motifs dans une seule regex. La position ne correspond que si tous nos motifs correspondent.

Si nous permettons la réutilisation infinie de lettres de la phrase originale (comme Knuth fit selon le commentaire de glenra), alors il est encore plus facile de construire une regex:

sentence = "Ziegler's Giant Bar" 

# find all the letters in the sentence 
letters = sentence.downcase.gsub(/[^a-z]/,'').split(//).uniq 

# construct a regex that matches any line in which 
# the only letters used are the ones in the sentence 
regex = /^([^a-z]|[#{letters.join}])*$/i 

# open a big file of words, and find all the ones that match 
words = File.open("/usr/share/dict/words") do |f| 
    f.map { |word| word.chomp }.find_all { |word| regex =~ word } 
end 

words.length #=> 6725 
words #=> ["A", "a", "aa", "aal", "aalii", "Aani", "Ab", "aba", "abaiser", "abalienate", 
      ... 
      "azine", "B", "b", "ba", "baa", "Baal", "baal", "Baalist", "Baalite", 
      "Baalize", "baar", "Bab", "baba", "babai", "Babbie", "Babbitt", "babbitt", 
      ... 
      "Britannian", "britten", "brittle", "brittleness", "brittling", "Briza", 
      "brizz", "E", "e", "ea", "eager", "eagerness", "eagle", "eagless", "eaglet", 
      "eagre", "ean", "ear", "earing", "earl", "earless", "earlet", "earliness", 
      ... 
      "eternalize", "eternalness", "eternize", "etesian", "etna", "Etnean", "Etta", 
      "Ettarre", "ettle", "ezba", "Ezra", "G", "g", "Ga", "ga", "gab", "gabber", 
      "gabble", "gabbler", "Gabe", "gabelle", "gabeller", "gabgab", "gabi", "gable", 
      ... 
      "grittiness", "grittle", "Grizel", "Grizzel", "grizzle", "grizzler", "grr", 
      "I", "i", "iba", "Iban", "Ibanag", "Iberes", "Iberi", "Iberia", "Iberian", 
      ... 
      "itinerarian", "itinerate", "its", "Itza", "Izar", "izar", "izle", "iztle", 
      "L", "l", "la", "laager", "laang", "lab", "Laban", "labara", "labba", "labber", 
      ... 
      "litter", "litterer", "little", "littleness", "littling", "littress", "litz", 
      "Liz", "Lizzie", "Llanberisslate", "N", "n", "na", "naa", "Naassenes", "nab", 
      "Nabal", "Nabalite", "Nabataean", "Nabatean", "nabber", "nabla", "nable", 
      ... 
      "niter", "nitraniline", "nitrate", "nitratine", "Nitrian", "nitrile", 
      "nitrite", "nitter", "R", "r", "ra", "Rab", "rab", "rabanna", "rabat", 
      "rabatine", "rabatte", "rabbanist", "rabbanite", "rabbet", "rabbeting", 
      ... 
      "riteless", "ritelessness", "ritling", "rittingerite", "rizzar", "rizzle", "S", 
      "s", "sa", "saa", "Saan", "sab", "Saba", "Sabaean", "sabaigrass", "Sabaist", 
      ... 
      "strigine", "string", "stringene", "stringent", "stringentness", "stringer", 
      "stringiness", "stringing", "stringless", "strit", "T", "t", "ta", "taa", 
      "Taal", "taar", "Tab", "tab", "tabaret", "tabbarea", "tabber", "tabbinet", 
      ... 
      "tsessebe", "tsetse", "tsia", "tsine", "tst", "tzaritza", "Tzental", "Z", "z", 
      "za", "Zabaean", "zabeta", "Zabian", "zabra", "zabti", "zabtie", "zag", "zain", 
      ... 
      "Zirian", "Zirianian", "Zizania", "Zizia", "zizz"]