Rubyで組み合わせの取り出しを行う関数＜combination＞を作ってみた．permutationの結果で逆から見て同じものはいらない場合の話．

きっかけ

かの有名なTravelingSalesman問題を勉強中に，各点を巡回した場合の距離の最小値を探そうとしたのですが．各点へ行く順番の組み合わせを求める必要があったのでそのお話．

例）
とあるセールスマンが[1, 2, 3, 4]の御宅を回って本社に戻る．どの順番で行けば一番距離が短くて済む？
って問題なので0 = 本社とした場合に[0, 1, 2, 3, 4, 0]や[0, 3, 2, 1, 4, 0]等々の全通りでどれが一番距離が短いかを調べたい！

RubyのArrayクラスには標準でpermutationメソッドという順序を考慮した組み合わせを返してくれるメソッドがありまして，それを使うと以下の様になりますね．

nums = [1, 2, 3]
nums.permutation(3) do |item|
  p item
end

__END__
以下出力結果
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

この出力って順序逆にしたら同じだよねということに気づきました！
配列の順序を逆転して同じ順序の配列は不要なので，そう行った配列を返さないメソッドを自分で作ろうかなと思います

しかし！！！
もしかしたら標準ライブラリ等のどこかにそんなメソッドははすでに存在しているのかもしれませんね．

でもまぁ僕は作ってみます

メソッド

とりあえずコードをぺたり

def combination(hashes: [{id: Int, x_point: Float, y_point: Float}], from_index: Int, to_index: Int)
  exchanges = [] # 各組み合わせ結果を追加していく配列
  count = 0 # forの繰り返しの回数
  first_array_nums = [] # count_in_same_first_array_num毎に配列先頭の要素を追加していく
  count_in_same_first_array_num = 1 # 配列先頭の要素が同じ組み合わせの個数
  for i in 0...(to_index - from_index)
    count_in_same_first_array_num *= (to_index - 1 - from_index - i + 1)
  end
  hashes[from_index..to_index].permutation(to_index - from_index + 1) do |item|
    first_array_nums << item[0][:id] if count % count_in_same_first_array_num == 0
    exchanges << item if !first_array_nums.include?(item.last[:id])
    count += 1
  end
  exchanges
end

今回はあくまで，TravelingSalesman問題を扱うので各点のデータを[{id: Int, x_point: Float, y_point: Float}]の形式で格納している程で使えるメソッドです．

解説

僕はこの様にまず考えました．

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

#上から見た配列の要素0番目が，それ以降の配列の最後尾にきている配列は重複している！ 

そこで各配列の先頭の値をfirst_array_numsにappendしていきます．

しかし同じ数字ばかりappendしても使い勝手が悪い変数になるので，配列先頭の要素が同じ組み合わせの個数をcount_in_same_first_array_numに代入するのでこれを目安にfirst_array_numsに値をapendしていきます．

count_in_same_first_array_num の値は(先頭以外の要素の数)!の値なので以下の様に決定する．

for i in 0...(to_index - from_index)
  count_in_same_first_array_num *= (to_index - 1 - from_index - i + 1)
end

そして'first_array_nums'含まれる数字が要素0番目にくる組み合わせは返り値には加えない様にしています！

これでおしまい．

補足

引数のfrom_index: Int, to_index: Intはhashesの要素の何番目から何番目まででこのメソッドで出力するかを決めています．(よく考えたら，それは引数に値を代入する場合に[1..5]みたいな感じですればいいかも)