Jak pogrupować dwie tablice wartości na tablice wartości n w poniższym przykładzie?

Question

mam już wiele dwie tablice wartości na przykład w poniższej

ary = [[1, 2], [2, 3], [1, 3], [4, 5], [5, 6], [4, 7], [7, 8], [4, 8]] 

Chcę grupować je w

[1, 2, 3], [4, 5], [5, 6], [4, 7, 8] 

Ponieważ znaczenie jest 1 i 2 mają związek, 2 i 3 mają związek, 1 i 3 mają związek, więc 1,2,3 wszyscy mają relację

Jak mogę to zrobić za pomocą biblioteki ruby ​​lub dowolnego algorytmu?

Answer 1

Oto realizacja Ruby podstawowego Bron–Kerbosch algorithm:

class Graph 
    def initialize(edges) 
    @edges = edges 
    end 

    def find_maximum_cliques 
    @cliques ||= [] 
    bron_kerbosch([], nodes, []) if @cliques.empty? 

    @cliques 
    end 

    private 

    def nodes 
    @nodes ||= @edges.flatten.uniq 
    end 

    def neighbours 
    @neighbours ||= nodes.map do |node| 
     node_neighbours = 
     @edges.select { |edge| edge.include? node }.flatten - [node] 

     [node, node_neighbours] 
    end.to_h 
    end 

    def bron_kerbosch(re, pe, xe) 
    @cliques << re if pe.empty? && xe.empty? 

    pe.each do |ve| 
     bron_kerbosch(re | [ve], pe & neighbours[ve], xe & neighbours[ve]) 
     pe -= [ve] 
     xe |= [ve] 
    end 
    end 
end 

---

edges = [[1, 2], [2, 3], [1, 3], [4, 5], [5, 6], [4, 7], [7, 8], [4, 8]] 

Graph.new(edges).find_maximum_cliques # => [[1, 2, 3], [4, 5], [4, 7, 8], [5, 6]] 

Jest optymalizacja, które mogą dostać się do O(3^n/3).

Answer 2

macierzy mogą być postrzegane jako wykres (np Node Node 1 i 2 są połączone krawędzią, a także węzeł 2 i 3, ...)

Patrzysz na tablicę wszystkich maximum cliques. A clique cover to tablica z maksymalną liczbą kliknięć, która zawiera każdy węzeł dokładnie jeden raz. Ten problem to hard.

Klik jest podzbiorem wykresu, w którym każdy węzeł jest ze sobą połączony. Jeśli węzeł nie jest połączony z żadnym innym, tworzy klika z samym tylko jednym węzłem. Maksymalna klika to klika, której nie można powiększyć przez dodanie kolejnego węzła.

Ten gem może być w stanie pomóc, korzystając z metody all_max_cliques. Oto skrypt można napisać u podstaw kliki projektu:

require_relative 'src/graph.rb' 
require_relative 'src/bron.rb' 
require_relative 'src/max_clique.rb' 
require_relative 'src/util.rb' 
require 'set' 

ary = [[1,2],[2,3],[1,3],[4,5],[5,6],[4,7],[7,8],[4,8]] 

graph = Graph.new 
graph = ary.each_with_object(Graph.new){|(n1,n2),graph| graph.insert(n1, [n2])} 

all_max_cliques(graph.graph) 

wyprowadza:

intersections after sort!: {3=>[2], 2=>[3]} 
cliqueeee[3, 2, 1] 
intersections after sort!: {3=>[1], 1=>[3]} 
... 
... 
cliqueeee[6, 5] 
intersections after sort!: {5=>[]} 
cliqueeee[5, 6] 
largest clique!: [6, 5] 
[[3, 2, 1], [8, 7, 4], [6, 5]] 

Pamiętaj, że jeśli chcesz kliki pokrywę, (czyli partition), powinien pojawić się każdy węzeł dokładnie raz. 5 i 6 tworzą maksymalną klikę, a 4 jest już w środku [4,7,8], więc nie ma potrzeby, aby [4,5].

Oto bardzo podstawowe rozwiązanie typu bruteforce. Nie używaj go do niczego wielkiego!

require 'set' 

class Graph 
    attr_reader :nodes, :edges 

    def initialize(edges) 
    @nodes = edges.flatten.sort.uniq 
    @edges = edges.map(&:sort).to_set 
    end 

    def minimum_clique_cover 
    partitions.select{ |p| all_cliques?(p) }.min_by(&:size) 
    end 

    private 

    def partitions(array = nodes) 
    if array.length == 1 
     [[array]] 
    else 
     *head, tail = array 
     partitions(head).inject([]) do |result, partition| 
     result + (0..partition.length).collect do |index_to_add_at| 
      new_partition = partition.dup 
      new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [tail] 
      new_partition 
     end 
     end 
    end 
    end 

    def all_cliques?(partition) 
    partition.all?{ |subset| clique?(subset) } 
    end 

    def clique?(subset) 
    subset.permutation(2).select{ |n1, n2| n2 > n1 }.all?{ |edge| edges.include?(edge) } 
    end 
end 

p Graph.new([[1, 2], [2, 3], [1, 3], [4, 5], [5, 6], [4, 7], [7, 8], [4, 8]]).minimum_clique_cover 
# => [[4, 7, 8], [5, 6], [1, 2, 3]] 

Zwraca minimalną pokrywę kliki, która jest trudniejsza niż tylko Tablica maksymalnych klik. Nie pytaj mnie o złożoność tego scenariusza i nie będę musiał kłamać.