arrays - 如何在下面的示例中将两个值数组分组为 n 个值数组？

Question

我已经有很多两个值数组，例如下面的例子

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

我想把它们分组到

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

因为意思是1和2有关系，2和3有关系，1和3有关系，所以1,2,3都有关系

我如何通过 ruby​​ 库或任何算法来做到这一点？

Answer 1

这是基本 Bron–Kerbosch algorithm 的 Ruby 实现:

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

有一个优化可以让它达到O(3^n/3)。