質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.51%

  • Ruby

    8954questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • Ruby on Rails

    8372questions

    Ruby on Railsは、オープンソースのWebアプリケーションフレームワークです。「同じことを繰り返さない」というRailsの基本理念のもと、他のフレームワークより少ないコードで簡単に開発できるよう設計されています。

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 78

knt_krmt

score 1

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
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • maisumakun

    2019/03/13 17:38

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

    キャンセル

  • knt_krmt

    2019/03/13 19:30

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

    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と分けたいのですが数が多くなると処理時間が増えるので。

    キャンセル

回答 3

checkベストアンサー

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+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


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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • Ruby

    8954questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • Ruby on Rails

    8372questions

    Ruby on Railsは、オープンソースのWebアプリケーションフレームワークです。「同じことを繰り返さない」というRailsの基本理念のもと、他のフレームワークより少ないコードで簡単に開発できるよう設計されています。