擅长排列的小明
时间限制： 1000 ms | 内存限制：65535 KB
难度： 4
- 描述
- 小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。
- 输入
- 第一行输入整数N（1<N<10）表示多少组测试数据， 每组测试数据第一行两个整数 n m (1<n<9,0<m<=n) 输出
- 在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例 样例输入
-
23 14 2
样例输出 -
123121314212324313234414243 看到此题首先想到的使用递归方法实现，可以画出递归树结构，难点在于，利用深度遍历的同时，还要考虑到下一次遍历的数值不能和原来的重复。变换成树结构的话，子节点的数值不能与父节点及其父节点（祖辈节点）的数值相同。我们需要有一个数组结构来保存其祖辈节点。我首先使用的方法是在每一个节点都构造一个二维数值，利用二维数值的逻辑与或来保存父辈节点。但是还要考虑输出情况，输出是要从上往下的。所以我构造了一个树结构来还原这个递归遍历过程。 下面是我的代码：
#include
#include struct Node{ int data; int ids;// 保存祖辈节点 Node* parent;// 父节点用于递归输出};void outPut(Node* node){ if(node->parent != NULL) outPut(node->parent); if(node->data != 0) printf("%d", node->data);}void loop(Node* node, int n, int m){ int count = 1, i = 1; if(m < 1) { outPut(node); printf("\n"); return; } for(;count <= n;count++) { if((node->ids & (1 << count)) != 0) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->ids = node->ids & (~(1 << count)); newNode->parent = node; newNode->data = count; loop(newNode, n, m-1); } }}int main(){ int N = 0; scanf("%d", &N); while(N--) { int n = 0, m = 0, count = 1, i = 0; scanf("%d%d", &n, &m); Node* node = (Node*)malloc(sizeof(Node)); node->ids = 0xFFFFFFFF; node->data = 0; node->parent = NULL; loop(node, n, m); } return 1;} 程序虽然速度还可以，但是占用空间较大。使用了树结构。
然后我看了下最优代码，发现可优化的空间非常大。
首先，保存祖辈节点的结构使用了两个数组来代替。一个used数组，用来记录使用过的数值（也就是祖辈节点），用过的键值对应的是1，没有是0；一个char数组，用来保存祖辈节点的顺序性（如 “12” “21”）。
然后在递归遍历的同时，反复使用这两个数组记录祖辈节点，而不是每次递归到一个节点就记录一次。
仔细想想，递归常常跟树结构相伴而生。树结构如果只需要一次遍历的话，只依靠递归就可以解决，但是递归不具有重现性，因为通过函数栈push到内存空间，然后pop后里面的所有参数和局部变量就不存在了。而我们自行构造的树结构可以保存在堆空间里，可以重现遍历操作。
本题的最优解，就是最大程度的利用了递归方法，考略到需要适度的重现其祖父节点，就添加了两个全局数组变量。一定程度上弥补了递归的不可重现性。但是，也并没有实现完全可重现，全局变量需要高度重用。我实现的程序虽然占用了大量空间，但是却完整保留了递归的遍历过程。如果说给出任意一个节点，我就可以重现出关于它的遍历过程。
就本题来讲，当然是追求最快的速度和最小的空间。完全不用完整保存遍历过程，所以见招拆招才是最有效的。
最优解：
#include
#include #include #include using namespace std;int n,m,used[10];char ans[11];void dfs(int x,int num){ if(num==m-1) { ans[m]='\0'; printf("%s\n",ans); return; } int i; for(i=1;i<=n;i++) { if(!used[i]) { used[i]=1; ans[num+1]=i+'0'; dfs(i,num+1); used[i]=0; } }}int main(){ int i,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { memset(used,0,sizeof(used)); used[i]=1; ans[0]=i+'0'; dfs(i,0); } } return 0;}