einen Zyklus in einem gegebenen Array Detecting

-1

Ich habe eine Reihe von Zeichenfolgen, wie die folgenden:einen Zyklus in einem gegebenen Array Detecting

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

Dies stellt eine teilweise Ordnung, so dass "c" vor "b" ist, "f" vor "c" ist, "a" vor "d" ist, und "b" ist vor "e".

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

Wenn ich wie folgt ein Array: Die Bestellung kann in einem Gesamtauftrag wie realisiert werden

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

es keine partielle Ordnung darstellen, da es einen Zyklus.

Wie kann ich überprüfen, dass dies auftritt, wenn ein Array in mein Programm kommt?

Quelle

2016-04-23 Reiss Johnson

In technischer Hinsicht Sie versuchen Zyklen in einem gerichteten Graphen zu erkennen. Es gibt viele gute Diskussionen hier: http://stackoverflow.com/questions/261573/best-algorithm-for-detecing-cycles-in-a-directed-graph und natürlich Google. –

Frage ist nicht gut angegeben. Welche Variationen gibt es für den Teilstring, der die beiden Knoten begrenzt, außer '" => "', '" => ", und" "=>" '? Oder mussten Sie Ihre Frage in einem solchen konstruierten Format überhaupt erst formulieren? Könnte es nicht wie "[[a", nil], ["b", "c"], ["c", "f"], ...] sein? – sawa

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

den erfassten Zyklus zurückzukehren, ändern Sie die Zeile:

break !b.empty? if b == a

zu:

break b if b == a

Quelle

2016-04-23 03:45:13 sawa

ich folgendes tun würde.

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

Wenn

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

und n = 3

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

Wir werden diese enumerator in ein Array umwandeln können, die Elemente zu sehen, die an sie übergeben wird Block ist:

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 die Henne Kombination is_comb?

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

geben berechnen wir

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

Quelle

2016-04-26 01:37:56

einen Zyklus in einem gegebenen Array Detecting

Antwort

Verwandte Themen