初学者によるプログラミングMemo #21 順列


はじめに

今回は順列のお話です
Twitterで問題が回ってきたので解いてみました
Rails関係なくても書いている下記はすでに決まり文句ともなりました
なお、本記述はMacにおいて、Railsでの開発を前提としています
また、まだまだひよっこですので、不備等ございましたらご指摘いただけると幸いです
*例によって、問題の解釈を間違えていましたので、全体的に修正をいたしました
最初にご覧いただいた50名ほどのかた、大変失礼いたしました

目次

  • 順列とは
  • 問題を解いてみる

順列とは

あるn個のものの中から、k個を選び、順番をつけて並べられたもののことを言います
「組み合わせ」とは区別されており、「組み合わせ」は順番は関係ありません
実際に順列をみてみましょう

ここに、1,2,3のトランプが一枚ずつあります
このトランプの並べ方は何通りあるでしょう
…と聞かれたとします

そうすると

# 1,2,3
# 1,3,2
# 2,1,3
# 2,3,1
# 3,1,2
# 3,2,1

この6通りが挙げられます
このように、順番が違えば、それぞれを違うものとみなすことが順列の定義です

問題を解いてみる

Twitterで、以下のような問題が回ってきました

*3つの分数を足した結果が1になると言う数式
問題:
上記の数式の□(四角)のなかに、1~9までの文字を一文字ずつ入れて、等式を完成させなさい

わかりにくかったらすみません
まず、それぞれの四角を区別します

このようにして、a~iのなかにそれぞれ数字を当てはめていきます
まずは1~9が入った配列を作りましょう

*bc,ef,hiは共に二桁の整数です
私は解くときにここを間違えていました

array =[]
1.upto(9) do |i|
  array << i
end

これがいいか

array = [1,2,3,4,5,6,7,8,9]

これがいいかわかりませんが、どっちも結果は同じです
下の方が冗長でなくていいですが、応用はききにくいです(分数が倍になってしまったら、その分手打ちしないといけない)

そして、先ほどのa~iのなかに数字を入れていきます
a~iのなかに数字を入れていくには順番が大事ですよね
なので、ここで順列を使います

array =[]
1.upto(9) do |i|
  array << i
end

pat = array.permutation.to_a

permutationメソッドが出てきました
これが順列を作り出してくれます
公式リファレンスを置いておきます

これでpatのなかに、全通りの順列が入りました
ちなみに362,880通りです(9の階乗)
この中から単純に数式に当てはめて解きましょう

array =[]
1.upto(9) do |i|
  array << i
end

pat = array.permutation.to_a
ans = []
pat.each do |i|
# 間違っていましたので訂正いたします コメント欄参照
  x = (i[0].quo(i[1]*10 + i[2])) + (i[3].quo(i[4]*10 + i[5])) + (i[6].quo(i[7]*10 + i[8]))
  if x == 1
    ans << i
  end
end

p ans
# => [[5, 3, 4, 7, 6, 8, 9, 1, 2], [5, 3, 4, 9, 1, 2, 7, 6, 8], [7, 6, 8, 5, 3, 4, 9, 1, 2], 
#     [7, 6, 8, 9, 1, 2, 5, 3, 4], [9, 1, 2, 5, 3, 4, 7, 6, 8], [9, 1, 2, 7, 6, 8, 5, 3, 4]]

lengthつけないと、127,584通り結果が返されるので注意してください
当てはまる順列は127,584通りあります
確率にすると30%弱なので、適当に数字を入れても正解しそうです笑

…どころか、6種類しかないですね
しかも、足し合わせる分数三つを「順列」とした場合は解は6個ですが、「組み合わせ」 の場合解は1つのみです
(1+2+3=6,2+3+1=6 この二つの式はどちらも6になるので、組み合わせとしては同じ、と言う考え方)

さいごに

問題出題者(この記事においては)なのに、問題の解釈を間違えて申し訳ございませんでした
毎度ご覧いただいてる@scivolaさんには本当に感謝しかないです
…が、こんな恥ずかしいご指摘をいただかないためにも、頑張りたいと思います