Perlで順列組合せの問題を解く

(1) 青・赤・黄・緑の4色のボールがあります。これを順番に並べる方法はいくつありますか？

(2) この中から2色選んで順番に並べる方法はいくつありますか？

(3) この中から2色選んで順番を考えずに組合せを作る方法はいくつありますか？

こういう問題を学生の頃やらされました。_nC_rなどを見るとイライラするという方も多いでしょう。

最近こういう問題を解くはめになり、Perlでプログラムを書き計算する方法を調べてみました。もちろん数学の公式をネットで調べて当てはめてもいいのですが、既存のモジュールを使わない手はありません。

Math::Countingを使う

Math::Countingがこういうときはぴったり。

#!/usr/bin/env perl

use strict;
use warnings;
use Math::Counting;

# (1) 4色のボールを順番に並べる（4P4）

print P(4, 4);
print "\n";

# (2) 4色から2色選んで順番に並べる（4P2）

print P(4, 2);
print "\n";

# (3) 4色から2色選ぶ組合せ（4C2）

print C(4, 2);
print "\n";

出力は(1)は24、(2)は12、(3)は6となります。

ただ、答えだけを見せられても、私などは結果が本当かどうか不安になります。そこで、確認のために別のモジュールの登場です。

Math::Combinatoricsを使う

Math::Combinatoricsは実際の順列組合せを表示することができます。

#!/usr/bin/env perl

use strict;
use warnings;
use Math::Combinatorics;
use utf8;
binmode(STDOUT, ":utf8");

my @balls = qw(青 赤 黄 緑);

print "(1) 4色のボールを順番に並べる\n";
print join("\n", map { join " ", @$_ } permute(@balls));
print "\n";

print "(2) 4色から2色選んで順番に並べる\n";
print join("\n", map { join " ", @$_ } (map { permute (@$_) } combine(2, @balls)));
print "\n";

print "(3) 4色から2色選ぶ組合せ\n";
print join("\n", map { join " ", @$_ } combine(2, @balls));
print "\n";

これを実行すると出力はこうなります。

(1) 4色のボールを順番に並べる
青 赤 黄 緑
青 赤 緑 黄
青 黄 赤 緑
青 黄 緑 赤
青 緑 赤 黄
青 緑 黄 赤
赤 青 黄 緑
赤 青 緑 黄
赤 黄 青 緑
赤 黄 緑 青
赤 緑 青 黄
赤 緑 黄 青
黄 青 赤 緑
黄 青 緑 赤
黄 赤 青 緑
黄 赤 緑 青
黄 緑 青 赤
黄 緑 赤 青
緑 青 赤 黄
緑 青 黄 赤
緑 赤 青 黄
緑 赤 黄 青
緑 黄 青 赤
緑 黄 赤 青
(2) 4色から2色選んで順番に並べる
青 赤
赤 青
青 黄
黄 青
緑 青
青 緑
赤 黄
黄 赤
緑 赤
赤 緑
黄 緑
緑 黄
(3) 4色から2色選ぶ組合せ
青 赤
青 黄
青 緑
赤 黄
赤 緑
黄 緑

ちゃんと(1)が24通り、(2)が12通り、(3)が6通りということがわかります。(2)の場合のインターフェイスがよくないですが、一から自分でやることをかんがえればずっと良いというものです。