在枚舉數組時通過動態刪除數組中的元素

Question

我正在瀏覽我的系統字典並根據嚴格定義查找任何其他單詞的子集或超集。

下面的實現不起作用，但如果它實現了，我認爲這將是非常有效的。我如何遍歷數組，並在迭代過程中從同一個數組中刪除項目？

def collect_dead_words 
    result = @file #the words in my system dictionary, as an array 
    wg = WordGame.new # the class that "knows" the find_subset_words & 
        # find_superset_words methods 
    result.each do |value| 
    wg.word = value 
    supersets = wg.find_superset_words.values.flatten 
    subsets = wg.find_subset_words.values.flatten 
    result.delete(value) unless (matches.empty? && subsets.empty?) 
    result.reject! { |cand| supersets.include? cand } 
    result.reject! { |cand| subsets.include? cand } 
    end 
    result 
end 

注：find_superset_words和find_subset_words都返回哈希值，因此values.flatten位

Answer 1

這就是我想出了根據您的反饋（加用最短的話開始進一步優化）受歡迎的！

Answer 2

這是不可取的，而遍歷它來修改的集合。相反，要麼迭代集合的副本，要麼創建一個單獨的數組以便稍後移除。

Answer 3

完成此操作的一種方法是使用Array＃delete_if。這是我在運行它，所以你得到的想法：

def collect_dead_words 
    result = [] 
    collection = @file 
    num = @file.max_by(&:length).length 
    1.upto(num) do |index| 
    subset_by_length = collection.select {|word| word.length == index } 
    while !subset_by_length.empty? do 
     wg = WordGame.new(subset_by_length[0]) 
     supermatches = wg.find_superset_words.values.flatten 
     submatches = wg.find_subset_words.values.flatten 
     collection.reject! { |cand| supermatches.include? cand } 
     collection.reject! { |cand| submatches.include? cand } 
     result << wg.word if (supermatches.empty? && submatches.empty?) 
     subset.delete(subset_by_length[0]) 
     collection.delete(subset_by_length[0]) 
    end 
    end 
    result 
end 

進一步優化：

supersets_and_subsets = [] 

result.delete_if do |el| 
    wg.word = el 
    superset_and_subset = wg.find_superset_words.values.flatten + wg.find_subset_words.values.flatten 
    supersets_and_subsets << superset_and_subset 

    !superset_and_subset.empty? 
end 

result -= supersets_and_subsets.flatten.uniq 

Answer 4

問題

據我所知，串s1是串s2的一個子集，如果之後的零個或多個字符從s2除去s1 == s2;即，如果存在映射的索引的ms1使得：

• 每個索引i的s1，s1[i] = s2[m(i)];和
• if i < j then m(i) < m(j)。

此外s2是s1的超集當且僅當是s1的s2一個子集。

請注意，對於s1成爲s2的子集，s1.size <= s2.size必須爲真。

例如：

• 「貓」是「工藝」，因爲如果「r」和「F」被除去後者成爲「貓」的子集。
• 「貓」不是「可愛」的子集，因爲「可愛」沒有「a」。
• 「貓」不是「at」的超集，因爲「cat」.include？（「at」）＃=> true`。
• 「貓」不是「制定」的子集，因爲m(0) = 3和m(1) = 2，但m(0) < m(1)是錯誤的;

算法

子集（並因此超集）是一個傳遞關係，其允許算法顯著效率。我的意思是，如果s1是s2的子集並且s2是s3的子集，則s1是s3的子集。

我將如下進行：

• 創建空集neither_sub_nor_sup和longest_sups和空數組subs_and_sups。
• 按字長排序單詞，最長的第一個。
• 將w加上neither_sub_nor_sup，其中w是字典中最長的單詞。
• 對於字典中的每個字隨後w（最長至最短），執行以下操作：
  • 爲每個元素的neither_sub_nor_supu確定是否w是u一個子集。如果是，請將u從neither_sub_nor_sup移動到longest_sups，並將u附加到subs_and_sups。
  • 如果一個或多個元素從neither_sub_nor_sup移動到longest_sups，則附加w到subs_and_sups;否則將w加到neither_sub_nor_sup。
• 返回subs_and_sups。

代碼

require 'set' 

def identify_subs_and_sups(dict) 
    neither_sub_nor_sup, longest_sups = Set.new, Set.new 
    dict.sort_by(&:size).reverse.each_with_object([]) do |w,subs_and_sups| 
    switchers = neither_sub_nor_sup.each_with_object([]) { |u,arr| 
     arr << u if w.subset(u) } 
    if switchers.any? 
     subs_and_sups << w 
     switchers.each do |u| 
     neither_sub_nor_sup.delete(u) 
     longest_sups << u 
     subs_and_sups << u 
     end 
    else 
     neither_sub_nor_sup << w 
    end 
    end 
end 

class String 
    def subset(w) 
    w =~ Regexp.new(self.gsub(/./) { |m| "#{m}\\w*" }) 
    end 
end 

例

dict = %w| cat catch craft cutie enact trivial rivert river | 
    #=> ["cat", "catch", "craft", "cutie", "enact", "trivial", "rivert", "river"] 
identify_subs_and_sups(dict) 
    #=> ["river", "rivert", "cat", "catch", "craft"] 

變

不像從最長的詞典處理的話至最短，我們可以代替他們最短責令最長：

def identify_subs_and_sups1(dict) 
    neither_sub_nor_sup, shortest_sups = Set.new, Set.new 
    dict.sort_by(&:size).each_with_object([]) do |w,subs_and_sups| 
    switchers = neither_sub_nor_sup.each_with_object([]) { |u,arr| 
     arr << u if u.subset(w) } 
    if switchers.any? 
     subs_and_sups << w 
     switchers.each do |u| 
     neither_sub_nor_sup.delete(u) 
     shortest_sups << u 
     subs_and_sups << u 
     end 
    else 
     neither_sub_nor_sup << w 
    end 
    end 
end 

identify_subs_and_sups1(dict) 
    #=> ["craft", "cat", "rivert", "river"] 

基準

（未完待續......）

^{1 OP指出（在後面的評論），其s1是不是s2的子字符串，如果s2.include?(s1) #=> true。我會假裝我從來沒有看到過，因爲它將扳手投入作品。不幸的是，subset不再是與附加要求的傳遞關係。我沒有調查這個問題的含義，但我懷疑這意味着需要一個相當粗暴的算法，可能需要對詞典中所有單詞進行兩兩比較。}