ACMXMU-OJ:1005

题目 1005.Complete Permutation

Description

Generate the complete permutation of  1..N

Input

Each input file contains only one non-negative integer N (0< N < 9)

Output

Output N! Lines, according to lexicographic order.

Sample Input

3

Sample Output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

想法

一开始想到用递归来写全排列，就课本上的方法，结果才发现输出时最后两个的次序不对。先试了试STL中的next_permutation函数，后面又自己写了个字典序法全排列。这里简述一下字典序法全排列

1. 待排列“字符串”： $P_0P_1P_2..P_{j-1}P_jP_{j+1}..P_n$
2. 从后往前搜索，直到找到这样的一个数，它的下标为 j，且满足 $P_{j} < P_{j+1}$。此时有： $$P_{j} < P_{j+1} > P_{j+2} > P_{j+3} > .... > P_{n}$$ 即从P{j+1} 到 P{n}，它们是按字典序递减的。
3. 再次从后向前搜索，直到找到这样的一个数，它的下标为 k，且满足 $P_{k} > P_{j}$。$P_k$的位置如下： $$P_0P_1P_2..P_{j-1}P_jP_{j+1}....P_{k-1}P_{k}P_{k+1}....P_n$$
4. 交换$P_{k}$和$P_{j}$的值，这时候“字符串”为： $$P_0P_1P_2..P_{j-1}P_kP_{j+1}....P_{k-1}P_{j}P_{k+1}....P_n$$ 这时候得到的“字符串”会比原本的“字符串”大,但并不是所有大于“原字符串”中最小的。
5. 结合由（2）得到的大小关系,以及 $P_{k} > P_{j}$，可以得到交换后的“字符串”大小关系如下: $$....P_k<P_{j+1}>P_{j+2}>....>P_{k-1}>P_{j}>P_{k+1}....>P_n$$ 所以在最后一步中，把 P{j+1}P{j+2}….P_{n} 反转过来。最后得到： $$P_0P_1P_2..P_{j-1}P_kP_{n}..P_{j}..P_{j+1}P_{j+2}P_{j+1}....P_n$$ 这样得到的新“字符串”是大于“原字符串”中最小的。

提交

字典序法全排列

先贴代码

#include <iostream>
#include <stdio.h>
using namespace std;
int arrays[10];
int main()
{
    int number;
    int q;
    scanf("%d",&number);
    for(q = 1;q <= number;q++)
        arrays[q] = q;

    while(true){
        int j,k;
        int q;
        for(q = 1;q < number;q++)
            printf("%d ",arrays[q]);
        printf("%d\n",arrays[number]);
        for(j = number;j > 0;j--)
            if(arrays[j] < arrays[j+1])
                break;
        if(j == 0)
            break;
        for(k = number;k > j;k--)
            if(arrays[k] > arrays[j])
                break;
        int temp;
        temp = arrays[j];
        arrays[j] = arrays[k];
        arrays[k] = temp;
        int i1,i2;
        for(i1 = j+1,i2 = number;i1 < i2;i1++,i2--)
        {
            int temp;
            temp = arrays[i1];
            arrays[i1] = arrays[i2];
            arrays[i2] = temp;
        }
    }
    return 0;
}

使用STL

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
    int number;
    scanf("%d",&number);
    int a[11];
    int i;
    for(i = 0;i < number;i++)
        a[i] = i + 1;
    do{
        int k;
        for(k = 0;k < number - 1;k++)
            printf("%d ",a[k]);
        printf("%d\n",a[number - 1]);
    }
    while (next_permutation(a,a+number));
    return 0;
}

递归全排列，不合要求

#include <iostream>
#include <stdio.h>
using namespace std;
int number;
char arrays[11]="0123456789";
void Perm(int m);
int main()
{
    scanf("%d",&number);

    int i,j;
    Perm(1);
    return 0;
}
void Perm(int m){
    if (m == number){
       int i;
       for(i = 1;i < m;i++)
            printf("%c ",arrays[i]);
       printf("%c\n",arrays[m]);
    }
    else
    {
        int i,j;
        for(j = m;j <= number;j++){
            int temp;
            temp = arrays[j];
            arrays[j] = arrays[m];
            arrays[m] = temp;
            Perm(m+1);
            temp = arrays[j];
            arrays[j] = arrays[m];
            arrays[m] = temp;
        }
    }
}