permutation と combination

Ruby の permutaion は リストから 組み合わせを簡単に列挙してくれます。

例えば [1,2,3,4] から 任意の3つの数字を抽出する組み合わせは以下のように簡単に記述できます。

[1,2,3,4].permutation(3).to_a.each do |l| p l end
[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

Scala だと permutations がありますが、Rubyのように これ一発では出来ないので combination と併せてつかう。

scala> List(1,2,3,4).combinations(3).flatMap(_.permutations).toList.foreach(println(_))
List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)
List(1, 2, 4)
List(1, 4, 2)
List(2, 1, 4)
List(2, 4, 1)
List(4, 1, 2)
List(4, 2, 1)
List(1, 3, 4)
List(1, 4, 3)
List(3, 1, 4)
List(3, 4, 1)
List(4, 1, 3)
List(4, 3, 1)
List(2, 3, 4)
List(2, 4, 3)
List(3, 2, 4)
List(3, 4, 2)
List(4, 2, 3)
List(4, 3, 2)

Permutation は順列 Combination は組み合わせ になります。 高校の時に確率統計で習った気がします。

例えば 1 から 4 までの数字の組み合わせは と言う問題だとすると

Ruby だと

p [1,2,3,4].permutation(4).to_a.count

と記述することで 24 通りあることがわかります。

１から4までの数字から二つ取り出す組み合わせは

p [1,2,3,4].combination(2).to_a.count

と すると6 通りということがわかります。