全配列非再帰

(二)非再帰的な全配列アルゴリズム
アルゴリズムの考え方:
1つのシーケンスについて、firstで開始位置、lastで終了位置、区間で[first,last]と表すことができ、初期状態のシーケンスの値は増加する.
1、隣接する2つのデータ(i=last-1、j=last、毎回比較後i--かつj--)を後から前へ比較し、前者が後者より小さい場合(*i<*j、*iはi位置に対応する値を示す)、前者の値がX 1(X 1=*i)(位置PX=i)であることを示す.
2、再度X 1以下の最初のデータを後から前へ検索し、値はX 2とする.
3、交換X 1、X 2;
4、[PX+1,last]マーク範囲を逆にする.
ポイント:なぜこれで最小限の増加が保証されるのか.
隣接する2つのデータを後方から比較すると,上記のアルゴリズムは位置PXを得ると,[PX+1,last]は常に減少し,[first,PX)は変化せず,[PX+1,last]の全配列が得られたことを意味する.X 2位置後の値はX 1よりも小さく、X 2位置前の値はX 1よりも大きいため、X 1,X 2を交換した後も[PX+1,last]は減少する.X 2>X 1であるため、X 2の後ろがどのように並んでも元の数列より大きくなり、[PX+1,last]を反転してこのサブ数列(インクリメント)を最小にする.
これにより、保証される新しい数列は、元の数列の辞書順にnextを配列する.
コード#コード#

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

//  
void Swap(char *a, char *b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}

void Reverse(char *a, char *b)
{
    //    
    while(a < b)
        Swap(a++, b--);
}

bool Permutation(char a[], int n)
{
    char *pEnd = a + n -1;
    char *p, *q, *pFind;

    p = pEnd;

    while(p != a)
    {
        q = p;
        p--;                    //p    ，q    

        if(*p < *q)             //      
        {
            pFind = pEnd;       //        
            while(*pFind <= *p) //      p    
                --pFind;
            Swap(pFind, p);     //  
            Reverse(q,pEnd);    //  
            return true;
        }
    }
    return false;               //        
}
int main()
{
    char a[100];
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
        a[i] = i+'1';
    a[n] = '\0';
    int i = 1;
    do{
        printf(" %3d   \t%s
", i++, a);
    }while (Permutation(a, n));
    return 0;
}