トップページに戻る    次のJavaScriptのサンプルへ    前のJavaScriptのサンプルへ

Q31 ソートされないカード


JavaScriptのソース

Solve(4);
Solve(8);

function Solve(pN)
{
    var wkJyunretu = DeriveJyunretu(pN);

    const UB = pN - 1;

    var Answer = 0;
    for(var EachInd in wkJyunretu){
        var wkArr = wkJyunretu[EachInd].concat();
        for(var I = 0 ; I <= UB ; I++){
            var wkVal1 = wkArr[I];
            var wkVal2 = wkArr[wkArr[I]-1];
            wkArr[wkArr[I]-1] = wkVal1;
            wkArr[I] = wkVal2;
        }

        var IsOK = true;
        for(var I = 0 ; I <= UB ; I++)
            if(I + 1 != wkArr[I]) IsOK = false;

        if(IsOK == false){
            //document.write(JSON.stringify(wkJyunretu[EachInd]) , 'は昇順に並びません。' ,
            //    JSON.stringify(wkArr) , 'で終了します。' , '<br>');
            Answer++;
        }
    }
    document.write('N=' , pN , 'だと' , Answer , '通り<br>');
}

//コンストラクタ
function JyoutaiDef()
{
    this.CurrArr = new Array();
}

//1からNまでの数値の順列を返す
function DeriveJyunretu(pN)
{
    var JyunretuArr = new Array();

    var Stk = new Array();
    var WillPush = new JyoutaiDef();
    Stk.push(WillPush);
    while(Stk.length > 0){
        var Poped = Stk.pop();

        //クリア判定
        if(Poped.CurrArr.length == pN){
            JyunretuArr.push(Poped.CurrArr);
            continue;
        }

        for(var I = 1 ; I <= pN ; I++){
            if (Poped.CurrArr.indexOf(I) >= 0) continue;
            WillPush = new JyoutaiDef();
            WillPush.CurrArr = Poped.CurrArr.concat();
            WillPush.CurrArr.push(I);

            Stk.push(WillPush);
        }
    }
    //document.write(JSON.stringify(JyunretuArr));
    return JyunretuArr;
}


実行結果

N=4だと3通り
N=8だと28630通り


解説

ナイーブにシュミレーションしてます。