異なるn個から異なるm個を選び出す場合の、全てのパターンを得たい。

PC版へ 2013年10月07日

いわゆる「重複なしの組み合わせ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;
}

?>

こんな感じで使います。

<?php
$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個を選び出したときの、全ての組み合わせパターンを求めよ」などと無茶を言われても安心。ま、そんなことを要求される場面は余り想像つきませんが。

関連記事

コメント

現在、コメント機能は停止しています。