如何用非递归的算法来求解一个"全排列"

linux_c_py_php

参考STL：nth_element, 实现参考:<<STL源码剖析>>.

本人很久没碰C++, 表示对C++无感.

__BlueGuy__

cjaizss 发表于 2012-09-18 16:44
正好之前写了个

一个 DFS 能写成这样， 也算是一朵奇葩...

__BlueGuy__

不知道楼主高中有没学过数学， 全排列怎么算的知道吗 ？？

cjaizss

__BlueGuy__ 发表于 2012-09-22 12:16
一个 DFS 能写成这样， 也算是一朵奇葩...

你写的好，你来写吧

cjaizss

__BlueGuy__ 发表于 2012-09-22 12:21
不知道楼主高中有没学过数学， 全排列怎么算的知道吗 ？？

如果真要开骂，我就开骂了。
我不明白你的逻辑怎么就和常人不一样，没明白你怎么看出LZ的题目和全排列怎么计算有关系的。

__BlueGuy__

cjaizss 发表于 2012-09-22 13:02
如果真要开骂，我就开骂了。
我不明白你的逻辑怎么就和常人不一样，没明白你怎么看出LZ的题目和全排列怎 ...

笑而不语~~

cjaizss

__BlueGuy__ 发表于 2012-09-22 13:10
笑而不语~~

滚吧

__BlueGuy__

全排列最直接的解法就是 for循环， 而递归不过是 for循环的简化
高中生都会解的算法，被你写的这么高深， 佩服, 佩服~~

全排列是最简单的 dfs 模型， 人尽皆知

楼主的本质问题是不知道怎么把 递归dfs 转化成 非递归dfs，
也就是说楼主根本没理解 递归dfs， 要不然不可能转化不了， 是个人都会转的~~

还有， 这种小儿科的代码， 我才不屑写呢
还有，楼主的水平实在太菜了， 这都搞不定，~~

笑而不语

cjaizss

__BlueGuy__ 发表于 2012-09-22 13:19
全排列最直接的解法就是 for循环， 而递归不过是 for循环的简化
高中生都会解的算法，被你写的这么高深，  ...

递归的长什么样啊？请教

__BlueGuy__

cjaizss 发表于 2012-09-22 13:46
递归的长什么样啊？请教

好吧

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define NUM 4
   
5. #define MAX_DEPTH 2
   
6. 
   
7. int mark[NUM+1] = {0};
   
8. int printList[NUM+1] = {0};
   
9. 
   
10. void dfs(int depth);
    
11. 
    
12. int main(void)
    
13. {
    
14.     dfs(1);
    
15.     return 0;
    
16. }
    
17. 
    
18. void dfs(int depth)
    
19. {
    
20.     int i;
    
21. 
    
22.     for (i = 1; i <= NUM; i++)
    
23.     {
    
24.         if (!mark[i])
    
25.         {
    
26.             mark[i] = 1;
    
27. 
    
28.             printList[depth] = i;
    
29. 
    
30.             if (depth < MAX_DEPTH)
    
31.             {
    
32. 
    
33.                 dfs(depth+1);
    
34.             }
    
35.             else
    
36.             {
    
37.                 int j;
    
38. 
    
39.                 for (j = 1; j <= MAX_DEPTH; j++)
    
40.                 {
    
41.                     printf("%d ", printList[j]);
    
42.                 }
    
43. 
    
44.                 printf("\n");
    
45.             }
    
46. 
    
47.             mark[i] = 0;
    
48.         }
    
49.     }
    
50. }
    

复制代码