全配列アルゴリズムの詳細の生成

以下のアルゴリズムはすべてn個の異なる要素に基づいている.
アルゴリズム1:再帰+遡及+SWAP.出力を無視して、毎回再帰的に満たす:T(n)=n*T(n-1)+O(n)はG(n)=T(n)/n!G(n)=G(n−1)+O(1/(n−1)!)を得た.だから:G(n)=Theta(1).T(n)=Theta(n!).だから時間の複雑さはTheta(n!)各配列は配列に対応し,空間的に複雑なO(n!)である.このアルゴリズムがなぜ実行可能なのかについて,式に基づいて証明する::n!=n*(n-1)(n-2)…*2*1全配列は初期にn個のスペースからなると仮定し,全配列を求めるのは最初のスペースからすべてのスペースを満たすことである.この呼び出し関数GetPermutation(int*a,int first,int end)ごとに3つの主要なステップがある:これが呼び出し関数GetPermutation(a,0,n-1)ステップ1であると仮定する:区間[0,n-1]から数TEMP 1を見つけて配列の最初のスペースに記入し、n種類(すなわち#のn項)、すなわちforループの意味を持つ.ステップ2:ステップ1に基づいて、区間[0+1,n-1]の配列を考慮し、当該区間についてステップ1を繰り返し、再帰呼び出しに属する(すなわち、当該区間の最初の数として1つの数を選択し、n-1の場合、すなわち#の(n-1)項がある).ステップ3:ステップ1のTEMP 1を元の位置に戻し、遡及に属する.残りのn−1個の数から、配列の最初のスペース、すなわちforサイクルのi++に1個の数TEMP 2を再検索する.

#include 
#include
using namespace std;
void SWAP(int &a, int &b){
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}
int sum=0;
void GetPermutation(int *a,int first,int end){// [first,end]        [first,end]  first
    if(first == end){//      
        sum++;
        for(int i = 0; i <= end; i++)
        cout<" ";
cout<else {
GetPermutation(a,first+1,end);//first  は  [first,end]の  の として、  [first+1,end]から1つをfirst+1として  する
for(int i=first+1;i<=end;i++){//このループは  [first+1,end] の  が[first+1,end] の  の として    されることを す
SWAP(a[first],a[i]);//  [first,end] のi  の を[first,end]の  の とする
GetPermutation(a,first+1,end);//  [first+1,end]から[first+1,end]の  の として  
SWAP(a[first],a[i]);//i  の を の  に し、i+1  の を  [first,end]の  の とする
}
}
}
int main() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n;
int a[100];
cout<<"Input the size of the array:"<cin>>n;
cout<<"Input elements of the array:"<for(int i=0;icin>>a[i];
}
GetPermutation(a,0,n-1);
cout<「  」<「   」;
return 0;
}

アルゴリズム2:ディクショナリシーケンスアルゴリズム+SWAP.このアルゴリズムの時間的複雑さは、入力列のディクショナリシーケンスサイズに基づいている.空間複雑度O(n).n個の異なる要素の辞書順も全部でnがあることを知っています.これは偶然ですか?観察:1,2,3の全配列:1,2,3;1,3,2;2,1,3,;2,3,1;3,1,2;3,2,1このソートはちょうど辞書順に増加していることが分かった.まさか全配列を求めるのはすべての辞書の順序を求めるのですか?答えは肯定的だ.与えられた列が配列の中で辞書の順序が最も小さいと仮定します(例えば、1,2,3,4,5).私たちの操作は、現在の配列の次の配列を探すたびに(「次の配列」は、現在の配列よりも大きい配列の中で最も小さいものをすべて指す)、最後に出力されるのは辞書順に1回増加するので、現在の配列の最後から検索します.ai>ai+1を検索すると,2つの数を交換することで辞書順のより小さな配列しか得られず,次の配列は得られない.したがって,ai+1より小さい対数aiを見つける必要があり,ai+1の後に減少するという最初の探索である.次の全配列を得るためには、aiの代わりにもっと大きな数を使う必要があります.つまり、位置を交換する必要があります.それはもちろん、その後ろからこの数を探しに行きます(全配列は増分出力なので、前の数は変更できません).そして、最小のものを探して、必ず見つけることができます.少なくともai+1があります.その後、交換後のi+1〜nのすべての数をインクリメンタルに配列する.このとき,次の配列が得られる.aiがai+1より小さい場合が見つからないまで、上記の操作を繰り返します.このアルゴリズムは,辞書シーケンスが与えられた列よりも大きいすべての配列しか求められず,n個の異なる要素の全配列が先に昇順ソートされなければならないことを要求する.

#include 
#include
using namespace std;
char a[100];
int len;
int sum=0;
void _qsort(char* str,int Start,int End){
    if(Start==End) return;//  
    char tmp=str[Start];
    int i=Start,j=End;
    while(iwhile(istr[j]>tmp) j--;
        str[i]=str[j];//  i  ，j     
        while(istr[i]str[j]=str[i];//  j  ，i     
    }
    str[i]=tmp;//  i  
    //     i=j
    if(i-1>Start)_qsort(str,Start,i-1);
    if(jstr,i+1,End);
}
void GetPermutation(char* str)
{
    if(!str)
        return;
    while(true)
    {
        sum++;
        cout <<str<int j=len-2,k=len-1;
        while(j>=0 && str[j]>str[j+1])
            --j;//       str[j]
        if(j<0) break;//   str[j]

        while(str[k]<str[j])
            --k;//       str[j]       

        char temp=str[k];//    
        str[k]=str[j];
        str[j]=temp;

        int a,b;//str[j]            
        for(a=j+1,b=len-1;astr[a];
            str[a]=str[b];
            str[b]=temp;
        }
    }
    cout<<sum<<"   "<int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>len;
    for(int i=0;i>a[i];
    }
    _qsort(a,0,len-1);
    GetPermutation(a);
    return 0;
}