ルビー：クラスカル法 - ResultArray操作

Question

私はルビーに新たなんだと私はクラスカル法で少しプレーしてきたが、現時点では、私はバンプをヒットしていると私は私が何をする必要があるか理解できませんこの段階では。

私が取り組んできたコードはこれです：私は最後の部分を除いてすべてを行うために管理

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

。

私はどのようにソートされた配列操作することは考えていない：私はすべての扱わ計算とedgeValuesに保存されているこれらの値を持っている

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

：最終的な結果を達成するために

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

をアレイ。

ご協力いただければ幸いです。

Answer 1

Kruskal's Algorithmのことを聞いたことがなかったので、私はそれが最低限のスパニングツリーを計算するための方法であることを見つけるためにそれを見上げました。 OPはここでそのアルゴリズムを採用したいと考えているが、その理由は述べていない。根本的な問題が取り上げられている声明もありません。この例では、並べ替えられた配列を最大でも1つの大きさが異なるように、指定された数の配列（ "クラスタ"）に分割することをオブジェクトが想定しています。もしそうであれば、最小限のスパニングツリーを見つけることの1つとして問題を表示しない、以下の私のソリューションを含め、それを行う方法はたくさんあります。

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