(36) 順列

3,496 views

この記事は最終更新から 1970日 が経過しています。

perms を使うとベクトル要素の順列 Permutation を生成できる。

octave:1> v = [3,5,2]
v =
   3   5   2

octave:2> perms(v)
ans =
   3   5   2
   5   3   2
   3   2   5
   5   2   3
   2   3   5
   2   5   3

nchoosek を使うとベクトル要素の中から任意個数の組み合わせ Combination を生成できる。

octave:3> v = [1:5]
v =
   1   2   3   4   5

octave:4> nchoosek(v,3)
ans =
   1   2   3
   1   2   4
   1   2   5
   1   3   4
   1   3   5
   1   4   5
   2   3   4
   2   3   5
   2   4   5
   3   4   5

ここで…
nPr を出したいのだが、perms では nPn は出せても nPr が出せない。

苦肉の策で以下のように perms と nchoosek を組み合わせて nPr を生成してみた。
絶対にスマートな方法があるはずなのだがわからない…

ここでは { 1, 2, 3, 4, 5 } の中から 3個を選ぶ ときの組み合わせを生成してみる。

octave:5> v = [1:5];
octave:6> n = 3;
octave:7> c = nchoosek(v,n);
octave:8> p = [];
octave:9> for i=1: size(c,1)
>     p = [p; perms(c(i,:))];
> end
octave:10> disp(p);
   1   2   3
   2   1   3
   1   3   2
   2   3   1
   3   1   2
   3   2   1
   1   2   4
   2   1   4
   1   4   2
   2   4   1
   4   1   2
   4   2   1
   1   2   5
   2   1   5
   1   5   2
   2   5   1
   5   1   2
   5   2   1
   1   3   4
   3   1   4
   1   4   3
   3   4   1
   4   1   3
   4   3   1
   1   3   5
   3   1   5
   1   5   3
   3   5   1
   5   1   3
   5   3   1
   1   4   5
   4   1   5
   1   5   4
   4   5   1
   5   1   4
   5   4   1
   2   3   4
   3   2   4
   2   4   3
   3   4   2
   4   2   3
   4   3   2
   2   3   5
   3   2   5
   2   5   3
   3   5   2
   5   2   3
   5   3   2
   2   4   5
   4   2   5
   2   5   4
   4   5   2
   5   2   4
   5   4   2
   3   4   5
   4   3   5
   3   5   4
   4   5   3
   5   3   4
   5   4   3
octave:11> disp(size(p));
   60    3

₅P₃の組み合わせ数を計算で求めると以下の通り。

(5 x 4 x 3 x 2 x 1) / (2 x 1)
= 5 x 4 x 3
= 60

正しく60通りの組み合わせを生成できているようだ。