ruby 組合せ 計算時間短縮方法

Question

e×2の数を2つで分けたい時の組合せを下のプログラムで表した、最終はm_0の前後で表している。
分ける際数字は小さいもの順に並べます。
e=100の時、200を2つに分ける時の組合せが多すぎて、時間が掛かってしまいます。その対処方法がわかる方いらっしゃいますか？？

e = gets.to_i
m = (e*2).times.map{|i| i+1 }.combination(e).to_a

m_0 = (m.count/2).times.map{|i|
 m[i]+m[m.count-i-1]
}
puts m_0

Comments

[maisumakun]

このままのコードではm_0の中身は「配列」となりますが、得たいものはそれで間違いないでしょうか？

[knt_krmt]

返事ありがとうございます。
はい、配列で間違いないです。

e=2の時

e = gets.to_i
m = (e*2).times.map{|i| i+1 }.combination(e).to_a

a = (m.count/2).times.map{|i|
m[i]
}
b = (m.count/2).times.map{|i|
m[m.count-i-1]
}
puts a => [[1, 2], [1, 3], [1, 4]]
puts b => [[3, 4], [2, 4], [2, 3]]

本当はこのようにa,bと分けたいのですが数が多くなると処理時間が増えるので。

Answer 1

combinationの順序は保証されないので、2つに分けたいのなら、順番に書けば良いのでは？

e = gets.to_i
open("a.txt","w") do |a|
open("b.txt","w") do |b|
  1.step(e*2).to_a.combination(e).each_slice(2) do |x,y|
    a.puts x.inspect
    b.puts y.inspect
  end
end;end

ディスクが足りないと思いますけど。

そもそもから、考え直すべきですね。

Answer 2

e=100の時、200を2つに分ける時の組合せが多すぎて、時間が掛かってしまいます。

どうしようもありません。欲しい結果自体が膨大な配列である以上、回避するすべはありません。

Answer 3

200C100を計算させると分かりますが9e58という膨大な組み合わせが存在し
列挙するのは時間・メモリの都合上無理です。

他の条件ややり方を精査し、列挙しない方法を探すべきです。

---

ちなみに、n.times.map{|i|よりもArray.new(n){|i|の方が僅かにパフォーマンスがよいですし
この場合は、(1..e*2).to_aや[*1..e*2]のがラクかな　と思います。

m_0 = (m.count/2).times.map{|i|
  m[i]+m[m.count-i-1]
}
puts m_0

なにやってるのか分かりづらいですし、るりまによるとcombinationで得られる組み合わせの順序は保証されていないらしいので
常に正しいかはわかりません。

all = [*1..e*2]
m = all.combination(e).to_a
m_0 = m.select{|a|a.include? 1}.map{|a| [a, all-a]}

こんな感じのほうが読みやすいと思いますよ