紅寶石在維持秩序的同時用子串創建句子

Question

我目前正在研究一個Ruby問題，其中我基本上是在創建自己的語言。下面（名詞，動詞，文章）可以被認爲是單詞。然而，爲了創造一個有效的句子，我必須有一個動詞，一個名詞或者至少兩篇文章。

名詞： 「ABCD」， 「C」， 「DEF」， 「H」，「IJ， 「CDE」

動詞： 「BC」， 「FG」， 「G」， 「HIJ」， 「BCD」

文章：「一」，「交流」，「E」

所以我試圖做的基本上是寫將一個字符串返回所有可能的有效句子（同時保持字符的方法以相同的順序在詞語之間插入空格）

例如輸入= "abcdefg" 返回列表

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

所以，我想打破這個問題，這是我迄今爲止

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"] 

我的思維過程是我第一次希望得到所有可能的組合爲每個單詞（名詞，動詞，文章）。我不確定這是否是解決這個問題最有效的方法，但除了這一步之外，我還沒有成功地嘗試形成有序的句子。

我一直在搜索堆棧和其他網站的組合/排序技術的類型，再加上我正試圖避免使用正則表達式。我誠摯地感謝任何方向/反饋，以便如何繼續我的旅程來解決這個問題。感謝您的時間！

Answer 1

很可能沒有正則表達式，但你有一個困難時期沒有遞歸寫什麼：

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) 

它輸出：

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

這裏是寫一個遞歸方法的另一種方式。

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 

例

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"] 

注

對於該示例中，散列gram計算如下。

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} 

注意，以及映射詞轉換成語音的部分，我已刪除了幾個「字」不能是「句」 str的一部分。

我感到那

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} 

本來比原來grammar（「POS」的「詞性」），更方便的數據結構。

Answer 3

使用遞歸和lambda在紅寶石解決：

@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 

輸入：abcdefg

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