PIPIOJ 1130: 奇偶交错排列

1130: 奇偶交错排列

题目描述

如果一个1~N的排列P = [A1, A2, … AN] 满足任意两个相邻整数都是一个奇数另一个偶数，我们就称P是奇偶交错排列。

给定一个N，请你按字典序输出所有1~N的奇偶交错排列。

输入

多组数据

一个整数N。 1 <= N <= 11

输出

输出若干行，每行一个排列，每个数字后面一个空格。

样例输入

4

样例输出

1 2 3 4  
1 4 3 2  
2 1 4 3  
2 3 4 1  
3 2 1 4  
3 4 1 2  
4 1 2 3  
4 3 2 1

思路 1

调用库函数再验奇偶。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, arr[12];while(scanf("%d", &n) != EOF){
    for(int i = 0; i < n; i++)arr[i] = i + 1;do{
    bool flag = true;for(int i = 1; i < n; i++){
    if((arr[i] & 1) == (arr[i - 1] & 1)){
    flag = false;break;}}if(flag)for(int i = 0; i < n; i++)printf("%d%c", arr[i], i == (n - 1) ? '\n' : ' ');}while(next_permutation(arr, arr + n));}return 0;
}

思路 2

回溯法，回溯法生成全排列，且在回溯搜索过程中只枚举有效状态（奇偶交错），因此效率更高。

时间复杂度分析：

? 1.当 n 为奇数时，一共有 （n / 2 + 1) ! * (n / 2) ! 种有效方案；

? 2.当 n 为偶数时，一共有 2 * (n / 2) ! * (n / 2) ! 种有效方案；

? 3.因此时间复杂度为 o (((n / 2) !) ^ 2)。

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int vis[N], ans[N], n;
void dfs(int x)
{
    if(x == n){
    for(int i = 0; i < n; i++)printf("%d%c", ans[i], i == (n - 1) ? '\n' : ' ');return;}for(int i = 1; i <= n; i++){
    if(vis[i] == 0 && (x == 0 ||(ans[x - 1] & 1) != (i & 1))){
    ans[x] = i;vis[i] = 1;dfs(x + 1);vis[i] = 0;}}
}
int main()
{
    while(scanf("%d", &n) != EOF){
    memset(vis, 0, sizeof(vis));dfs(0);}return 0;
}