AOJ基础题 ITP2_5_C+D Permutation 全排列

Permutation

For given a sequence A={a0, a1, … , an−1}, print the previous permutation and the next permutation in lexicographic order.

Input

A sequence is given in the following format.

n
a0 a1 ...  an−1

Constraints

1 ≤ n ≤ 9
ai consist of 1, 2, … , n

Output

Print the previous permutation, the given sequence and the next permutation in the 1st, 2nd and 3rd lines respectively. Separate adjacency elements by a space character. Note that if there is no permutation, print nothing in the corresponding line.

Sample Input 1

3
2 1 3

Sample Output 1

1 3 2
2 1 3
2 3 1

Sample Input 2

3
3 2 1

Sample Output 2

3 1 2
3 2 1

問題を解く

初见用了最简单的解法，然后根据输出结果一遍遍改条件，实际上这样效率挺慢的。

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>

using namespace std;

int a[9] = { 0 };

void myPrint(int* num, int n)
{
    int d = 0;
    for (int i = 0; i < n; i++)
    {
        if (num[i] != a[i]) {
            d = 1;
        }
    }
    if (d)
    {
        cout << num[0];
        for (int i = 1; i < n; i++)
        {
            cout << " " << num[i];
        }
        cout << endl;
    }
}

void myReverse(int* a, int left, int n)
{
    int temp = 0;
    int m = left;
    int k = n - 1;

    while (m < k)
    {
        swap(a[m], a[k]);
        m++;
        k--;
    }
}

void nextP(int* a, int n)
{
    int index = -1;
    for (int i = n - 1; i >= 1; i--)
    {
        if (a[i] > a[i - 1])
        {
            index = i - 1;
            break;
        }

    }
    if (index != -1)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            if (a[j] > a[index])
            {
                swap(a[j], a[index]);
                myReverse(a, index + 1, n);
                break;
            }
        }
    }
}

void preP(int* a, int n)
{
    int index = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (a[i] < a[i - 1])
        {
            index = i - 1;
            break;
        }

    }
    if (index != -1)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            if (a[j] < a[index])
            {
                swap(a[j], a[index]);
                myReverse(a, index + 1, n);
                break;
            }
        }
    }
}

int main() 
{
    int n;
    cin >> n;

    int next[9] = { 0 };
    int pre[9] = { 0 };

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        next[i] = a[i];
        pre[i] = a[i];
    }

    preP(pre, n);
    myPrint(pre, n);

    cout << a[0];
    for (int i = 1; i < n; i++)
    {
        cout << " " << a[i];
    }
    cout << endl;

    nextP(next, n);
    myPrint(next, n);

    return 0;
}

总结

想到一种递归的解法，刚好可以用到打印所有全排列的题目里：

void reP(int* a, int id, int n)
{
    if (id == n - 1)
    {
        cout << a[0];
        for (int i = 1; i < n; i++)
        {
            cout << " " << a[i];
        }
        cout << endl;
    }
    else
    {
        for (int i = id; i < n; i++)
        {
            swap(a[i], a[id]);
            reP(a, id + 1, n);
            swap(a[i], a[id]);
        }
    }
}

但是最终打印出的所有排列并不是按字典序排列的，需要手动再排一次（麻烦）。
网上查到说原因是数组指针的关系（引用会对原数组直接进行操作），如果用string或者vector来写就不会出现这个问题，也不用进行第二次swap。

当一个string对象作为参数传递给函数时，传递的是引用的一个copy，原来的引用没有改变。

当一个字符数组作为参数传递给函数时，传递的是这个数组的引用，对它进行函数处理，就是对原数组进行处理。

当然最方便的还是SLT中的next_permutation()函数，一步到位；

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() 
{
    int n;
    cin >> n;

    vector<int> v(n);

    for (int i = 0; i < n; i++) 
    {
        cin >> v[i];
    }

    vector<int> p(v), nx(v);
    prev_permutation(p.begin(), p.end());
    next_permutation(nx.begin(), nx.end());

    if (p < v) 
    {
        for (int i = 0; i < n; i++) 
        {
            if (i) 
            {
                cout << " ";
            }
            cout << p[i];
        }
        cout << endl;
    }
    for (int i = 0; i < n; i++) 
    {
        if (i) 
        {
            cout << " ";
        }
        cout << v[i];
    }
    cout << endl;

    if (nx > v) 
    {
        for (int i = 0; i < n; i++) 
        {
            if (i)
            {
                cout << " ";
            }
            cout << nx[i];
        }
        cout << endl;
    }
    return 0;
}