//  高橋グラフクラスライブラリー　工学者社用カスタマイズバージョン（H14.4.18）
//  順列クラス　実装ファイル    
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include "TKPermutateA.h"

    TKPermutate::TKPermutate()
{
        Size=0;
}
    TKPermutate::~TKPermutate()
{
}
//  基本機能
int TKPermutate::SetSize(int size)
{   //  次数を設定。
    if (size <= 0)
        return -1;  //  次数指定エラー
    if  (Size == size)
        return 0;   //  処理不要
    int ssave = Size;
    Size = size;
    if  (size > PMAX)
        size = PMAX;
//  階乗テーブル初期化
    memset(Fact,'\0',sizeof Fact);
    Fact[0]=1;  //  階乗初期設定
    int cnt;    //  ワークカウンター
    for (cnt=1;cnt<PMAX;cnt++)
        Fact[cnt] = Fact[cnt-1] * (cnt+1);  //  Fact[cnt]にcnt＋１の階乗を設定
    return 0;
}
int TKPermutate::GetSinglePerm(int num,uchar* ucp)
{   //  指定された番号に対する順列を返す
    unsigned char wp[PMAX],ucp1[PMAX+1];
    int i,k;
    memset(wp,'\0',sizeof wp);
    memset(ucp1,'\0',sizeof ucp1);

    num--;  // 1 count down
    for (i=Size;i>2;i--)
    {
        wp[i] = (int)(num / Fact[i-2]);
        num = num - wp[i] * Fact[i-2];
    }
    wp[2] = num;
    //  順列の取得
    ucp1[Size-wp[Size]] = Size;
    for (k=Size-1;k>1;k--)
    {
        int b = wp[k];
        for (int j = Size;j >= 0 && b > 0;)
        {
            if  (!ucp1[j--])
                b--;
        }
        while(ucp1[j])
            j--;
        ucp1[j] = k;
    }
    // 1を設定
    for (i=1;i<=Size;i++)
        if  (!ucp1[i])
        {
            ucp1[i] = 1;
            break;
        }
    memcpy(ucp,ucp1+1,Size);
    return 0;
}
int TKPermutate::GetNum(uchar* permp)
{   //  指定された順列に対応する番号を返す
    if  (!Size)
        return -1;
    uchar a[PMAX+1];
    int i;
    memset(a,'\0',sizeof a);
    //  引数が１からSizeまでの重複の無い数字であることを確認する。
    for (i=1;i<=Size;i++)
    {
        if  (permp[i-1] > Size || !permp[i-1])
            return -1;
        a[permp[i-1]]=i;    // a[i]に数字iの場所が入る。
    }
    for (i=1;i<=Size;i++)
        if  (!a[i])
            return -1;  // 重複があればどこかは０
    int s = Fact[Size-2]*(Size-a[Size]),k;
    for (i=Size-1;i>1;i--)
    {
        k=0;
        for (int j=i-1;j>=1;j--)
            if  (a[j]>a[i])
                k++;
        s +=  Fact[i-2]*k;
    }
    return s+1;
}
int TKPermutate::GetFact(int i)
{   //  指定された数の階乗を返す
    if (i < 1 || i > PMAX)
        return -1;
    return  Fact[i-1];
}

//  Ｎ−クイーン問題関連メンバー関数
int TKPermutate::IsQueen(uchar *in)
{
    if  (!Size || !in)
        return -1;
    for (int cnt1=1;cnt1<Size;cnt1++)
        for (int cnt2=0;cnt2<cnt1;cnt2++)
            if  (abs(in[cnt1]-in[cnt2])==cnt1-cnt2)
                return 0;
    return 1;
}
int TKPermutate::FormatDigit(uchar * in, char * out,char kugiri)
{   //  順列を＜・,・,・・・＞形式に変換する。
    if  (!in || !out || !Size)
        return -1;
    if  (Check(in)<0)
        return -1;
    if  (!kugiri && Size > 9) // 二桁で区切り無しはカンマを区切りとする
        kugiri = ',';
    char buff[100]="",buff1[5],fmt1[]="%d",fmt2[]="%d%c";
    int cnt,len;
    if  (!kugiri)   //  区切り無しの場合
    {
        for (cnt=0;cnt<Size;cnt++)
        {
            sprintf(buff1,fmt1,in[cnt]);
            strcat(buff,buff1);
        }
    }
    else    //  区切りがある場合
    {
        for (cnt=0;cnt<Size;cnt++)
        {
            sprintf(buff1,fmt2,in[cnt],kugiri);
            strcat(buff,buff1);
        }
        len = strlen(buff);
        buff[len-1]='\0';   //最後の区切りをはずす
    }

    strcpy(out,"<");
    strcat(out,buff);
    strcat(out,">");
    return strlen(out);
}
int TKPermutate::Check(uchar * p,char len)
{   //  引数が１からSizeまでの重複の無い数字であることを確認する。
    //  但し、lenが正の時は複数個の０が有っても良い。lenはその時のデータ長
    if  (!p || !Size)
        return -1;
    uchar w[PMAX];
    int cnt;
    memset(w,'\0',sizeof w);
    int s = Size;
    if  (len)
        s = len;
    for (cnt=1;cnt<=s;cnt++)
    {
        if  (p[cnt-1] > Size)
            return -1;
        if  (!len && !p[cnt-1])
            return -1;
        if (!p[cnt-1])
            continue;
        if  (w[p[cnt-1]-1])
            return -1;      //  重複あり
        w[p[cnt-1]-1] = 1;
    }
    return 0;   // OK
}