配列の実装

1136 ワード
コンポジット アルゴリズム#アルゴリズム# テキストリンク
[順番は?]
与えられた順序の任意の集合を異なる順序で混合する演算.
たとえば、[1,2,3]の数列がある場合、対応する順序は6種類あります.
**[1,2,3] 
[1,3,2] 
[2,1,3] 
[2,3,1] 
[3,1,2] 
[3,2,1]**
[next置換アルゴリズム]
この場合、これは、昇順に配列された数列に対して、降順に変換する過程で、次の数列の過程を意味する.
s{i|0<=i1.s(数列)について、s[i-1]2.1番で見つかったi-1について、s[i-1]3.s[i-1]s[j]を置き換えます.
4.s[i.n-1]を反転させます.
例)s=[1,4,3,2]
1) i=1, s[i]=4, s[i-1]=1
2) j=3, s[j]=2
3)s[i-1]=1とs[j]=2を交換すると、s=[2,4,3,1]となる.
4)[i~n-1]=>[1~3]をs=[2,1,3,4]に反転する.
[実装]
void reverse(string &s,int i,int n){
    for(;i<n;) swap(s[i++],s[n--]); 
 }
bool nextPermutation(string& s)
{
    // 1. s(수열)에 대해서 s[i-1]<s[i]를 만족하는 가장 큰수를 찾는다.
    // 2. 1번에서 찾은 i-1에 대하여 s[i-1]<s[j]를 만족하는 가장 큰 j를 찾는다
    // 3. s[i-1] s[j]를 바꿔치기한다.
    // 4. s[i..n-1]를 reverse시킨다.
    int i, j;
    i = j = s.size()-1;
    while (s[i - 1] >= s[i]) if (--i== 0) return false; //1번에 해당하는 i찾기
    while(s[j]<=s[i-1]) if(--j==0) return false; //2번에 해당하는 j찾기
    swap(s[j],s[i-1]);
    reverse(s,i,s.size()-1);
    return true;
}
シミュレーションマルチスレッドダウンロード
Mybatis一括書込み有則修正無則新規、同時に空選択書込みフィールドを判断