Chybeta

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

提交

字典序法全排列

先贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}

递归全排列,不合要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}
}
}
点击赞赏二维码,您的支持将鼓励我继续创作!
chybeta WeChat Pay

微信打赏

chybeta Alipay

支付宝打赏