GeneratingPermutations

离散数学的一个求下一个较大排列的算法

问题引入

Example: Permutation 23415 of set {1， 2， 3， 4， 5} precedes the per-
mutation 23514. Similarly, permutation 41532 precedes 52143.
Question: What is the next permutation in lexicographic order after
32541?

伪代码：

• 输入n个数，以-1结束，然后会输出下一个大的排列

1.首先让$aj$等于倒数第二个位置,然后和$a{j+1}$ 去相比。如果$aj>a{j+1}$ 那么j—, 一直比到 $aj<a{j+1}$ 为止

2.让$ak$ 等于倒数第一个位置，然后和当前的 $a_j$ 去比，如果$a_j>a{k}$ 那么k—, 一直比到 $a_j<a_k$ 为止

3.让$a_j$ 与 $a_k$ 交换

4.让现在$a_j$ 位置后面的数字按照从小到大排列。既可以是排序，也可以是头尾两两交换。

/*

输入：1432
At the begin , v[j] = 3
After the operation
v[j] = 1
At the begin , v[k] = 2
After the operation
v[k] = 2
After swap the v[j] and the v[k]
2 4 3 1
Then ,Range the Elems after v[j]
2 1 3 4

Finally ,The operation is  down ,and the next larger number is
2 1 3 4


输入：31528764
At the begin , v[j] = 6
After the operation
v[j] = 2
At the begin , v[k] = 4
After the operation
v[k] = 4
After swap the v[j] and the v[k]
3 1 5 4 8 7 6 2
Then ,Range the Elems after v[j]
3 1 5 4 2 7 6 8
3 1 5 4 2 6 7 8

Finally ,The operation is  down ,and the next larger number is
3 1 5 4 2 6 7 8



*/

#include<bits/stdc++.h>
using namespace std;
int n = 0;
void printv(vector<int>v)
{
    for(vector<int>::iterator it = v.begin();it!= v.end();it++)
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}
void swap(int &v1,int &v2)
{
    int temp = v1;
    v1=v2;
    v2= temp;
}
void ThenextLargerNumber(vector<int> &v)
{
    int j = n-2;
    cout<<"At the begin , v[j] = "<<v[j]<<endl;
    while(v[j]>v[j+1]) j = j -1;
    cout<<"After the operation "<<endl;
    cout<<"v[j] = "<<v[j]<<endl;
    int  k = n-1;
    cout<<"At the begin , v[k] = "<<v[k]<<endl;
    while(v[j]>v[k])
        k = k-1;
    cout<<"After the operation "<<endl;
    cout<<"v[k] = "<<v[k]<<endl;
    swap(v[j],v[k]);
    cout<<"After swap the v[j] and the v[k]"<<endl;
    printv(v);
    cout<<"Then ,Range the Elems after v[j]"<<endl;
    int r = n-1;
    int s = j+1;
    while (r>s)
    {

        swap(v[r],v[s]);
        printv(v);
        r--;
        s++;
    }
    cout<<endl;
    cout<<"Finally ,The operation is  down ,and the next larger number is "<<endl;
    printv(v);
}


int main()
{
    int num;
    cin>>num;
    vector<int>v;
    while(num!=-1)
    {
        while (num)
        {
            int temp = num%10;
            v.push_back(temp);
            num = num/10;
            n++;
        }
        reverse(v.begin(),v.end());
        ThenextLargerNumber(v);
        cout<<endl;
        v.clear();
        n=0;
        cin>>num;
    }


	return 0;
}

同理，我们也可以得到下一个较小排列的算法：

1.首先让$aj$等于倒数第二个位置,然后和$a{j+1}$ 去相比。如果$aj<a{j+1}$ 那么j—, 一直比到 $aj>a{j+1}$ 为止

2.让$ak$ 等于倒数第一个位置，然后和当前的 $a_j$ 去比，如果$a_j<a{k}$ 那么k—, 一直比到 $a_j>a_k$ 为止

3.让$a_j$ 与 $a_k$ 交换

4.让现在$a_j$ 位置后面的数字按照从大到小排列。既可以是排序，也可以是头尾两两交换。