異なるn個から異なるm個を選び出す場合の、全てのパターンを得たい。
いわゆる「重複なしの組み合わせ」nCm の話です。
例えば、
異なるn個のものから異なるm個のものを取り出す組み合わせは何通りあるか？
…という問題ならば、WikiPediaあたりにも書かれている公式を使えば簡単に求められるのですが、
異なるn個のものから異なるm個のものを取り出したときの全ての組み合わせを書き出せ。
…と言われると、ちょっと面倒くさい。
具体的に、
{ A , B , C , D , E } から、重複なしに3個取り出したときの全ての組み合わせは？
と、これくらいなら手作業でも出来るし、プログラミングする場合でも、安直にforループを3つネストさせれば出来る。
でも「20個から異なる4個を選んだときの組み合わせを全て書き出せ」なんて言われたら、手作業では煩わしい。20C4 = 4845 通りの組み合わせになりますからな。安直にforループを20個ネストさせれば出来るけれど、それでは汎用性が皆無。
で、こんな関数を作ってみたのですが、どうか。とりあえず PHP5 で書いてみた。単純な再帰アルゴリズムなので、すぐ別の言語にも書き換えられますね。
<?php
function getCpattern( $source, $m ){
/* 引数 $source：選択元要素の配列 */
/* 引数 $m：$source から異なる $m 個を選ぶ */
$n = sizeof($source);
return ptn( $source, $n, array(), 0, $n-$m+1 );
}
/* ptn：内部で再帰的に呼び出される関数 */
function ptn( $source, $n, $subset, $begin, $end ){
$p = array();
for( $i = $begin; $i<$end; $i++){
$tmp =array_merge( $subset, (array)$source[$i] );
if( $end+1 <= $n ){
$p = array_merge($p , ptn( $source, $n, $tmp, $i+1, $end+1 ) );
}else{
array_push( $p, $tmp );
}
}
return $p;
}
?>
function getCpattern( $source, $m ){
/* 引数 $source：選択元要素の配列 */
/* 引数 $m：$source から異なる $m 個を選ぶ */
$n = sizeof($source);
return ptn( $source, $n, array(), 0, $n-$m+1 );
}
/* ptn：内部で再帰的に呼び出される関数 */
function ptn( $source, $n, $subset, $begin, $end ){
$p = array();
for( $i = $begin; $i<$end; $i++){
$tmp =array_merge( $subset, (array)$source[$i] );
if( $end+1 <= $n ){
$p = array_merge($p , ptn( $source, $n, $tmp, $i+1, $end+1 ) );
}else{
array_push( $p, $tmp );
}
}
return $p;
}
?>
こんな感じで使います。
<?php
$source = array( 'A', 'B', 'C', 'D', 'E' ); //元の要素を格納した配列
$m = 3; // $source の中から重複なしで $m 個を選ぶ
$p = getCPattern( $source, $m ); //返ってくるのは全ての組み合わせを格納した配列
print_r( $p );//結果を表示
?>
$source = array( 'A', 'B', 'C', 'D', 'E' ); //元の要素を格納した配列
$m = 3; // $source の中から重複なしで $m 個を選ぶ
$p = getCPattern( $source, $m ); //返ってくるのは全ての組み合わせを格納した配列
print_r( $p );//結果を表示
?>
上記の結果は…
Array
(
[0] => Array
(
[0] => A
[1] => B
[2] => C
)
[1] => Array
(
[0] => A
[1] => B
[2] => D
)
[2] => Array
(
[0] => A
[1] => B
[2] => E
)
[3] => Array
(
[0] => A
[1] => C
[2] => D
)
[4] => Array
(
[0] => A
[1] => C
[2] => E
)
[5] => Array
(
[0] => A
[1] => D
[2] => E
)
[6] => Array
(
[0] => B
[1] => C
[2] => D
)
[7] => Array
(
[0] => B
[1] => C
[2] => E
)
[8] => Array
(
[0] => B
[1] => D
[2] => E
)
[9] => Array
(
[0] => C
[1] => D
[2] => E
)
)
組み合わせの個数を求めたければ、返り値 $p の sizeof() を見れば良いです。また、n < m の場合は、空の配列が返ってきます。
これで「50個の要素から異なる7個を選び出したときの、全ての組み合わせパターンを求めよ」などと無茶を言われても安心。ま、そんなことを要求される場面は余り想像つきませんが。
コメント