Ruby Erstellen von Sätzen mit Teilstrings unter Beibehaltung der Reihenfolge

Question

Ich arbeite derzeit an einem Ruby-Problem, in dem ich im Wesentlichen meine eigene Sprache erstelle. Unten (Substantive, Verben, Artikel) können als Wörter gedacht werden. Um jedoch einen gültigen Satz zu erstellen, muss ich ein Verb, ein Nomen oder mindestens zwei Artikel haben.

Substantive: "ABCD", "c", "def", "h", „ij "CDE"

Verb "bc", "fg", "g", "h ij", „bcd“

Artikel: „a“, „ac“, „e“

Also, was ich versuche, eine Methode im Grunde zu tun ist, schreiben die einen String und gibt alle möglichen gültigen Sätze nimmt (während Zeichen halten in der gleichen Reihenfolge und Einfügen eines Leerzeichens zwischen den Wörtern)

zB Eingabe = "abcdefg" zurück Die folgende Liste

[ "a bc def g", "a bcd e fg", "abcd e fg"] 

Also habe ich versucht, das Problem brechen und das ist, was ich

alpha = "abcdefg" 



nouns = ["abcd", "c", "def", "h", "ij", "cde"] 
verbs = ["bc", "fg", "g", "hij", "bcd"] 
articles = ["a", "ac", "e"] 

verbArray = []; 
nounArray = []; 
articleArray = []; 

nouns.each do |item| 
    if alpha.include?(item) 
    nounArray << item 
    end 
end 

verbs.each do |item| 
    if alpha.include?(item) 
    verbArray << item 
    end 
end 

articles.each do |item| 
    if alpha.include?(item) 
    articleArray << item 
    end 
end 


puts nounArray.inspect => ["abcd", "c", "def", "cde"] 
puts verbArray.inspect => ["bc", "fg", "g", "bcd"] 
puts articleArray.inspect => ["a", "e"] 

Mein Denkprozess war so weit haben, dass ich alle möglichen Kombinationen für jedes der Worte zuerst erhalten wollte (Substantive, Verb, Artikel). Ich bin mir nicht sicher, ob dies der effizienteste Weg ist, um dieses Problem anzugehen, aber über diesen Schritt hinaus habe ich versucht, ohne viel Erfolg, geordnete Sätze zu bilden.

Ich habe Stacks und andere Websites nach Arten von Kombinationen/Sortiertechniken gesucht, und ich versuche im Moment zu vermeiden, Regex zu verwenden. Ich würde ehrlich jede mögliche Richtung/Rückgespräch schätzen, wie man meine Reise fortsetzt, um dieses Problem zu lösen. Danke für Ihre Zeit!

Answer 1

Es ist möglich, ohne Regex, aber Sie werden es schwer haben, etwas ohne Rekursion zu schreiben:

grammar = { 
    noun: ["abcd", "c", "def", "h", "ij", "cde"], 
    verb: ["bc", "fg", "g", "hij", "bcd"], 
    article: ["a", "ac", "e"]} 

def find_sentences(text, grammar, head = [], structure = []) 
    if text.empty? 
    if structure.include?(:verb) || structure.include?(:noun) || structure.count(:article) > 2 
     puts "Sentence found : " 
     puts head.join(' ') 
     puts structure.join(' ') 
     puts 
    end 
    else 
    grammar.each do |type, words| 
     words.each do |word| 
     if text.start_with?(word) 
      find_sentences(text.slice(word.size..-1), grammar, head + [word], structure + [type]) 
     end 
     end 
    end 
    end 
end 

find_sentences("abcdefg", grammar) 

Es gibt:

Sentence found : 
abcd e fg 
noun article verb 

Sentence found : 
a bc def g 
article verb noun verb 

Sentence found : 
a bcd e fg 
article verb article verb 

Answer 2

Hier ist ein weiterer Weg, um eine rekursive Methode des Schreibens.

def all_sentences(str, grammar) 
    gram = grammar.each_with_object({}) { |(k,v),h| 
    v.select { |s| str.include?(s) }.each { |s| h[s] = k } } 
    recurse(str, gram.keys, gram, '') 
end 

def recurse(str, parts, gram, partial) 
    p = partial.delete(' ') 
    parts.each_with_object([]) do |part, arr| 
    combine = p + part 
    next unless str.start_with?(combine) 
    s = (partial + ' ' + part).lstrip 
    if combine.size == str.size 
     arr << s if valid?(s, gram) 
    else 
     arr.concat(recurse(str, parts, gram, s)) 
    end 
    end 
end 

def valid?(candidate, gram) 
    arr = candidate.split 
    arr.any? { |s| [:noun, :verb].include?(gram[s]) } || 
    arr.count { |s| gram[s] == :article } > 1 
end 

Beispiel

grammar = { 
    noun: ["abcd", "c", "def", "h", "ij", "cde"], 
    verb: ["bc", "fg", "g", "hij", "bcd"], 
    article: ["a", "ac", "e"] 
} 

str = "abcdefg" 

all_sentences(str, grammar) 
    #=> ["abcd e fg", "a bc def g", "a bcd e fg"] 

Hinweis

Für das Beispiel wird die Hash gram wie folgt berechnet.

gram = grammar.each_with_object({}) { |(k,v),h| 
    v.select { |s| str.include?(s) }.each { |s| h[s] = k } } 
    #=> {"abcd"=>:noun, "c"=>:noun, "def"=>:noun, "cde"=>:noun, 
    # "bc"=>:verb, "fg"=>:verb, "g"=>:verb, "bcd"=>:verb, 
    # "a"=>:article, "e"=>:article} 

Beachten Sie, dass sowie Mapping Worte in Teilen der Sprache, ich habe ein paar „Worte“ entfernt, die nicht Teil der „Satz“ str sein kann.

Es scheint mir, dass

words_to_pos = grammar.each_with_object({}) { |(k,v),h| v.each { |s| h[s] = k } } 
    #=> {"abcd"=>:noun, "c"=>:noun, "def"=>:noun, "h"=>:noun, "ij"=>:noun, 
    # "cde"=>:noun, "bc"=>:verb, "fg"=>:verb, "g"=>:verb, "hij"=>:verb, 
    # "bcd"=>:verb, "a"=>:article, "ac"=>:article, "e"=>:article} 

wäre eine bequeme Datenstruktur als der ursprüngliche grammar („po“ für „Wortart“) gewesen.

Answer 3

gelöst in rubin Rekursion und Lambda mit:

@nouns = ["abcd", "c", "def", "h", "ij", "cde"] 
@verbs = ["bc", "fg", "g", "hij", "bcd"] 
@articles = ["a", "ac", "e"] 
@return_arr = [] 
def solve(idx, hash, ans = []) 
    # base case 
    if (idx >= $str.length) and (hash['vs'] >= 1) and (hash['ns'] >= 1 or hash['as'] >= 2) 
     @return_arr << ans.join(" ") 
     return 
    end 
    # define lamda to do common operation 
    execute = lambda do |var, i| 
     hash[var] += 1 
     ans << $str[idx..i] 
     solve(i+1, hash, ans) 
     ans.pop 
     hash[var] -= 1 
    end 
    #check for nouns, verbs, articles 
    $str.each_char.with_index do |c,i| 
     next if i < idx 
     execute.call('ns', i) if @nouns.include? $str[idx..i] 
     execute.call('vs', i) if @verbs.include? $str[idx..i] 
     execute.call('as', i)if @articles.include? $str[idx..i] 
    end 
end 

$str = gets.strip 
hash = Hash.new(0) 
solve(0, hash) 
p @return_arr 

Eingang: abcdefg

Ausgang: ["a bc def g", "a bcd e fg", "abcd e fg"]