読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】重複組み合わせ。シンプル!

問題

0から9までの数字を重複を許して4つ選ぶ時、
答えはいくつありますか?

若干眠くて口調が変だよ。


(例)

0011 と 1001 と 0101 は同じ
1112 と 1122 は違う


 

答え(全列挙型Ver)

最初に思いついたのは、0~9999を全部並べて、一個ずつ確認する方法。
既に存在する組み合わせはスキップする。

result = []
i = 0
while i < 10000
  candidate = i.to_s.split("")
  (4 - candidate.length).times do
    candidate << "0"
  end
  candidate.sort!
  acceptable = true
  result.each do |data|
    if data == candidate #並び替えた後 既存と同じ組み合わせになる物は無視
      acceptable = false
      break
    end
  end
  result << candidate if acceptable
  i += 1
end
p result.length


 

答え(シンプルVer!)

どうやって解いたらもっとスマートかな??と探していたら
for文で事足りますよね、という記事を発見。
確かに!

result =[]
i = 0
while i < 10
  j = i
  while j < 10
      k = j
      while k < 10
        m = k
        while m < 10
          result << "#{i},#{j},#{k},#{m}"
          m += 1
        end
        k += 1
      end
    j += 1
  end
  i += 1
end
p result.length

早い!
すごい!