Ruby: Kruskal's Algorithm - ResultArray manipulation

Question

I'm new to Ruby and I've been playing with the Kruskal's Algorithm a little bit but at the moment I've hit a bump and I can't understand what I need to do at this stage.

The code I've been working on is this:

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

I managed to do everything except the last part.

I have no idea how to manipulate the sorted array:

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

In order to achieve the end result:

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

I have all the calculations handled and those values stored in the edgeValues array.

Any help would be appreciated.

Not asked but you do not need edgeValues = edgeValues.sort. It is enough to finish with edgeValues.sort or in your case probably edgeValues.sort.each_slice(clusters) — Saša Zejnilović

Cary Swoveland Cary Swoveland · Accepted Answer · 2017-06-07T18:43:22

Not having heard of Kruskal's Algorithm I looked it up to find that it is a method for computing a minimal spanning tree. The OP wishes to employ that algorithm here, but the reason for doing so is not stated. Neither is there a statement of the underlying problem being addressed. I assume from the example that the object is to partition a sorted array into a given number of arrays ("clusters") such that those arrays differ in size by at most one and the larger ones are to be at the beginning. If so, there are many ways of doing that--including my solution below--that do not view the problem as one of finding a minimal spanning tree.

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's Algorithm - ResultArray manipulation

1 Answers