算法设计与分析笔记（5）—排列数字-一一网

【摘要】题目要求：给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。输出所有的排列方法。题目分析：利用递归深搜，一种解空间是基于排列树，一种是直接进行dfs暴力。 .———–还有c++的STL容器有一个函数 next_permutation：求下一个排列组合
a.函数模板：next_permutation(arr, arr+size); b….

题目要求：给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
输出所有的排列方法。
题目分析：利用递归深搜，一种解空间是基于排列树，一种是直接进行dfs暴力。
.———–还有c++的STL容器有一个函数 next_permutation：求下一个排列组合

a.函数模板：next_permutation(arr, arr+size);
b.参数说明：
　　arr：数组名
　　size：数组元素个数
c.函数功能：返回值为bool类型，当当前序列不存在下一个排列时，函数返回false，否则返回true，排列好的数在数组中存储

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N=100;
int a[N];

int main()
{ cin>>n; for(int i=0; i<n; i++) { a[i]=i+1; } do { for(int i=0; i<n; i++) { cout<<a[i]<<" "; } cout<<endl; } while(next_permutation(a,a+n)); 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

c++排列树



#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N=100;
int a[N];
void dfs(int u)
{ if(u==n) { for(int i=1; i<=n; i++) printf("%d ",a[i]); puts(""); return; } for(int i=u; i<=n; i++) { swap(a[u],a[i]);//交换当前数和a[i]的位置 dfs(u+1);//递归 swap(a[u],a[i]);//恢复原状 }

}
int main()
{ cin>>n; for(int i=1; i<=n; i++) { a[i]=i; } dfs(1); 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
  37
  38

dfs暴力

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N=100;
int a[N];
bool st[N];

void dfs(int u)
{ if(u>n) { for(int i=1;i<=n; i++) printf("%d ",a[i]); puts(""); return; } for(int i=1; i<=n; i++) { if(!st[i]) { a[u]=i; st[i]=true;//标记一下 dfs(u+1);//递归 st[i]=false;//恢复原状 } }
}

int main()
{ cin>>n; dfs(1); 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
  37
  38
  39