初学者によるプログラミング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さんには本当に感謝しかないです
…が、こんな恥ずかしいご指摘をいただかないためにも、頑張りたいと思います
Author And Source
この問題について(初学者によるプログラミングMemo #21 順列), 我々は、より多くの情報をここで見つけました https://qiita.com/Ikuy_h/items/b15f4aeff1a3813f35f9著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .