Q13 並べ替えの繰り返し2

PHPのソース

<?php
ini_set('memory_limit', '256M');

Solve(4,3);
Solve(9,5);

//Nと処理回数を引数として解を返す
function Solve($pN , $pSyoriCnt)
{
    $JyunretuArr = DeriveJyunretuArr($pN);
    $Answer=0;

    foreach($JyunretuArr as $EachJyunretu){
        $wkArr = $EachJyunretu;
        for($I = 1 ; $I <= $pSyoriCnt ; $I++){
            $wkArr = DeriveRevArr($wkArr);
            if($wkArr[0] == 1){
                if($I == $pSyoriCnt){
                    $Answer++;
                    //printf('解%dを発見' . PHP_EOL , $Answer);
                    //var_export($EachJyunretu);
                }
                else break;
            }
        }
    }
    printf('N=%d,処理回数=%dでは、%d通り' , $pN , $pSyoriCnt , $Answer);
    echo PHP_EOL;
}

class JyoutaiDef
{
    public $CurrArr;
}

//1からNまでの順列の配列を返す
function DeriveJyunretuArr($pN)
{
    $WillReturn = array();

    $Stk = new SplStack();

    for($I = 2 ; $I <= $pN ; $I++){
        $WillPush = new JyoutaiDef();
        $WillPush->CurrArr = array($I);
        $Stk->push($WillPush);
    }

    while($Stk->isEmpty() == false){
        $Popped = $Stk->pop();
        if(count($Popped->CurrArr) == $pN){
            $WillReturn[] = $Popped->CurrArr;
            continue;
        }
        for($I = 1 ; $I <= $pN ; $I++){
            if(in_array($I,$Popped->CurrArr)) continue;
            $WillPush = clone $Popped;
            $WillPush->CurrArr[] = $I;
            $Stk->push($WillPush);
        }
    }
    return $WillReturn;
}

//先頭の値の分だけ、逆順にした配列を返す
function DeriveRevArr($pArr)
{
    $WillReturn = $pArr;
    $wkInd = $pArr[0]-1;
    for($I = 0 ; $I <= $wkInd ; $I++){
        $WillReturn[$I] = $pArr[$wkInd - $I];
    }
    return $WillReturn;
}

実行結果

N=4,処理回数=3では、4通り
N=9,処理回数=5では、28692通り

解説

深さ優先探索で順列を列挙してから、
シュミレーションしてます。