ｎ個の選択肢から重複しない全ての組合せを求める

仕事で、出くわした仕様でした。
仕様においては、選択肢の最大が5つという事で、5個をサンプルデータとして検証しています。
おそらく、n個でも行けるはずです。
たぶん…

$patern = array(
    'A' => 1,
    'B' => 2,
    'C' => 3,
    'D' => 4,
    'E' => 5,
);
$keys = array_keys( $patern );

print_r( CombinationPattern::getAll( $keys ) );
//CombinationPattern::getAll( $keys ) ;
exit;

//====================================================================================
class CombinationPattern {
    function getAll( &$pattern, $flag = false ){
        $ret = array();
        $max = count( $pattern );
        $num = $max;

        if( $flag ){
            for( $n = 1; $n < $num; $n ++ ){
                $list = array();
                //計算回数最適化
                $loop = gmp_intval( gmp_fact($max) ) /
                    ( gmp_intval( gmp_fact($n) ) * gmp_intval( gmp_fact( $max - $n ) ) );

                for( $na = 0; $na < $loop; $na ++ ) {
                    $tmp = CombinationPattern::_getOnce( $pattern, $max, $n, $list );
                    if( $tmp !== false ) $ret[] = $tmp;
                }
            }
        } else {
            for( $n = $num; $n > 0; $n -- ){
                $list = array();
                $loop = gmp_intval( gmp_fact($max) ) /
                    ( gmp_intval( gmp_fact($n) ) * gmp_intval( gmp_fact( $max - $n ) ) );

                for( $na = 0; $na < $loop; $na ++ ) {
                    $tmp = CombinationPattern::_getOnce( $pattern, $max, $n, $list );
                    if( $tmp !== false ) $ret[] = $tmp;
                    else echo "false\n";
                }
            }
        }

        return $ret;
    }

    function _getOnce( &$items, $max, $num, &$duplicate ) {
        $flag = false;
        if( $num == 1 ){
            $tmp = array();
            for( $n = 0; $n < $max; $n ++ ){
                $sum = $n + 1;
                if( !in_array( $sum, $duplicate ) ){
                    $tmp[] = $items[$n];
                    $duplicate[] = $sum;
                    return $tmp;
                }
            }
            return false;
        }

        for( $n = 0; $n < $max; $n ++ ){
            //初期化
            $tmp = array();
            $line= array();
            $sum = 0;

            $tmp[] = $items[$n];
            $line[] = $n;
            $sum = $n + 1;
            for( $na = 0; $na < $num -2; $na ++ ) {
                $idx = $na + ($n + 1);
                if( $idx >= $max ) $idx -=$max;
                $tmp[] = $items[$idx];
                $line[] = $idx;
                $sum *= $idx + 1;
            }
            $len = count( $line );
            $loop = $max - $len;
            for( $nb = 0; $nb < $loop; $nb ++ ){
                $idx = $line[$len-1] + $nb + 1;
                if( $idx >= $max ) $idx -= $max;
                $tmp[$len] = $items[$idx];
                $swp = $sum * ($idx + 1);

                //debug
                //$line[$len] = $idx;
                //for( $i = 0; $i < count($line); $i ++ )  echo "{$items[$line[$i]]} ";
                //echo " : {$swp}\n";

                if( !in_array( $swp, $duplicate ) ) {
                    $flag = true;
                    $duplicate[] = $swp;
                    break;
                }
            }
            if( $flag ) break;
        }
        if( !$flag ) {
            return false;
        }
        return $tmp;
    }
}