Ruby: Kruskal 算法 - ResultArray 操作

Question

我是 Ruby 的新手，我一直在玩 Kruskal 算法，但现在我遇到了一个问题，我不明白我需要做什么这个阶段。

我一直在处理的代码是这样的：

def partition(arr, clusters)
  edgeValues = []
  index1 = 0
  index2 = 1
  arr = arr.sort # [3, 4, 5, 5, 6, 10, 15, 20, 75, 80, 85]

  arr.length.times{
    val = (arr[index1]-arr[index2]).abs
    edgeValues << [ val, index1, index2]

    index1 += 1
    index2 += 1

    break if (arr.length == index2)
  }

  edgeValues = edgeValues.sort

  #p edgeValues[0][0] # value cost
  #p edgeValues[0][1] # index 1
  #p edgeValues[0][2] # index 2


end

array = [5, 4, 3, 5, 15, 20, 10, 80, 75, 6, 85] 
clusters = 3

partition( array, clusters ) #end result: [ [3, 4, 5, 5, 6], [10, 15, 20], [75, 80, 85] ]

除了最后一部分，我都做到了。

我不知道如何操作排序后的数组：

[3, 4, 5, 5, 6, 10, 15, 20, 75, 80, 85]

为了达到最终结果：

[ [3, 4, 5, 5, 6], [10, 15, 20], [75, 80, 85] ]

我处理了所有的计算并将这些值存储在 edgeValues 数组中。

如有任何帮助，我们将不胜感激。

Answer 1

没听说过Kruskal's Algorithm 我查了一下，发现这是一种计算最小生成树的方法。 OP 希望在这里使用该算法，但未说明这样做的原因。也没有说明正在解决的潜在问题。我从示例中假设对象是将排序数组划分为给定数量的数组 ("clusters")，这样这些数组的大小最多相差一个，而较大的数组位于开头。如果是这样，有很多方法可以做到这一点——包括我下面的解决方案——不会将问题视为寻找最小生成树的问题之一。

def similar_size_clusters(array, nbr_clusters)
  sorted = array.sort
  smaller_size, nbr_larger = sorted.size.divmod(nbr_clusters)
  nbr_clusters.times.each_with_object([]) do |i,a|
    a << sorted.shift(i < nbr_larger ? smaller_size + 1 : smaller_size)
  end
end

array = [5, 4, 3, 5, 15, 20, 10, 80, 75, 6, 85] 
(1..array.size).each { |i| puts "clusters = #{i}: #{similar_size_clusters(array, i)}" }

clusters =  1: [[3, 4, 5, 5, 6, 10, 15, 20, 75, 80, 85]]
clusters =  2: [[3, 4, 5, 5, 6, 10], [15, 20, 75, 80, 85]]
clusters =  3: [[3, 4, 5, 5], [6, 10, 15, 20], [75, 80, 85]]
clusters =  4: [[3, 4, 5], [5, 6, 10], [15, 20, 75], [80, 85]]
clusters =  5: [[3, 4, 5], [5, 6], [10, 15], [20, 75], [80, 85]]
clusters =  6: [[3, 4], [5, 5], [6, 10], [15, 20], [75, 80], [85]]
clusters =  7: [[3, 4], [5, 5], [6, 10], [15, 20], [75], [80], [85]]
clusters =  8: [[3, 4], [5, 5], [6, 10], [15], [20], [75], [80], [85]]
clusters =  9: [[3, 4], [5, 5], [6], [10], [15], [20], [75], [80], [85]]
clusters = 10: [[3, 4], [5], [5], [6], [10], [15], [20], [75], [80], [85]]
clusters = 11: [[3], [4], [5], [5], [6], [10], [15], [20], [75], [80], [85]]

Ruby: Kruskal 算法 - ResultArray 操作

Ruby: Kruskal's Algorithm - ResultArray manipulation

ruby

arrays

kruskals-algorithm