一個給定的陣列中檢測一個週期

Question

我有一個字符串象數組以下：

["a => ", "b => c", "c = > f", "d => a", "e => b", "f =>"] 

這表示不完整階使得"c"是"b"之前，"f"是"c"之前，"a"是"d"前，和"b"之前是"e"。的順序可以在一個總次序來實現，例如：

["f", "c", "b", "a", "d", "e"] 

如果我有一個這樣的數組：

["a => ", "b => c", "c = > f", "d => a", "e => ", "f => b"] 

它並不代表一個偏序，因爲有一個週期。

當數組進入我的程序時，我該如何檢查這種情況？

Answer 1

def cycled? a 
    a = a.map{|s| s.match(/(\w+)? ?= ?> ?(\w+)?/).captures} 
    .delete_if{|x, y| x.nil? or y.nil?} 
    loop do 
    nodes = a.flatten.uniq 
    b = a.dup 
    nodes.each{|e| b.reject!{|x, y| y == e} unless b.any?{|x, y| x == e}} 
    nodes.each{|e| b.reject!{|x, y| x == e} unless b.any?{|x, y| y == e}} 
    break !b.empty? if b == a 
    a = b 
    end 
end 

cycled?(["a => ", "b => c", "c = > f", "d => a", "e => b", "f =>"]) # => false 
cycled?(["a => ", "b => c", "c = > f", "d => a", "e => ", "f => b"]) # => true 

要返回的檢測週期，更改行：

break !b.empty? if b == a 

到：

​​

Answer 2

我會做到以下幾點。

def circular_dependencies?(arr) 
    (2..arr.size).any? { |n| arr.combination(n).any? { |comb| is_cycle?(comb) } } 
end 

def is_cycle?(comb) 
    a = comb.flat_map { |s| s.split /\s+=>\s+/ }.rotate 
    a.each_slice(2).all? { |l,f| l==f } 
end 

arr = ["a =>", "b => c", "c => f", "d => a", "e =>", "f => b"] 
circular_dependencies?(arr) 
    #=> true 

arr = ["a =>", "b => c", "c => f", "d => a", "e =>", "f => a"] 
circular_dependencies?(arr) 
    #=> false 

當

arr = ["a =>", "b => c", "c => f", "d => a", "e =>", "f => b"] 

和n = 3

enum = arr.combination(n) 
    #=> #<Enumerator: ["a =>", "b => c", "c => f", "d => a", "e =>", 
    #     "f => a"]:combination(3)> 

我們可以將此枚舉轉換成數組，以查看將要傳遞給它的元素是塊：

enum.to_a 
    #=> [["a =>", "b => c", "c => f"], 
    # ["a =>", "b => c", "d => a"], 
    # ["a =>", "b => c", "e =>"], 
    # ["a =>", "b => c", "f => b"], 
    # ["a =>", "c => f", "d => a"], 
    # ["a =>", "c => f", "e =>"], 
    # ["a =>", "c => f", "f => b"], 
    # ["a =>", "d => a", "e =>"], 
    # ["a =>", "d => a", "f => b"], 
    # ["a =>", "e =>", "f => b"], 
    # ["b => c", "c => f", "d => a"], 
    # ["b => c", "c => f", "e =>"], 
    # ** ["b => c", "c => f", "f => b"], 
    # ["b => c", "d => a", "e =>"], 
    # ["b => c", "d => a", "f => b"], 
    # ["b => c", "e =>", "f => b"], 
    # ["c => f", "d => a", "e =>"], 
    # ["c => f", "d => a", "f => b"], 
    # ["c => f", "e =>", "f => b"], 
    # ["d => a", "e =>", "f => b"]] 

W母雞組合

comb = ["b => c", "c => f", "f => b"] 

傳遞給is_comb?我們計算

a = comb.flat_map { |s| s.split /\s+=>\s+/ } 
    #=> ["b", "c", "c", "f", "f", "b"] 
b = a.rotate 
    #=> ["c", "c", "f", "f", "b", "b"] 
enum = a.each_slice(2) 
    #=> #<Enumerator: ["c", "c", "f", "f", "b", "b"]:each_slice(2)> 
enum.to_a 
    #=> [["c", "c"], ["f", "f"], ["b", "b"]] 
enum.all? { |l,f| l==f } 
    #=> true