一道排列题的做法讨论

key

题目大概是这样的：

定义desirable数：如果一个数的每一位都严格升序，则该数为desirable数。
如：123, 489, 2678
某人使用了一个desirable数做密码。现在你被告称这个密码的长度为N位，
请用程序排列出所有的可能性。

二楼开始讨论实现方法。

key

显然这是一道10选N的排列问题。最简单的做法就是用递归函数来实现。
这个递归函数的定义大概是这样：

列出desirable数：起始于b, 共n位
  相当于：
     * 列出第一位数 <1>
     * 在余下的数中做list_desirable(k+1, n-1)，这里k为上面列出来的数的值

对于<1>，直觉上我会列出b:9的所有数，但事实上只需要写出 b : 9 - n + 1 这些数则可。

由于程序需要打印所有的排列，所以需要一个数据结构来记录现在已经列出来的数。
我们知道，当递归前进一步时，这个记录添加一个数；递归完成一步后，这个记录会减少一个数，
是明显的LIFO结构，所以用堆栈来实现

于是pseudo-code可以这样写：

1. ADT list_stack {
   
2.    V[] {记录已经入栈的数}
   
3.    top : integer
   
4.   push(int x);
   
5.   pop();
   
6.   as_string() : string;
   
7.   is_empty() : boolean
   
8. }
   
9. 
   
10. list_desirable(list_stack, int begin, int num)
    
11. {
    
12.   for(k = begin : 9 - num + 1)
    
13.   {
    
14.     list_stack.push(k);
    
15.     if(num==1)
    
16.        print(list_stack);
    
17.    else
    
18.       list_desirable(list_stack, k+1, num-1);
    
19.    list_stack.pop();
    
20. }

复制代码

key

代码很短，直接贴代码好了。由于C++中的stack不支持遍历，只好用vector来做栈（其实应该用list）

1.   8 template<class T> void print_stack(vector<T> &s)
   
2.   9 {
   
3. 10     typename vector<T>::iterator it;
   
4. 11     for(it=s.begin(); it!=s.end(); it++)
   
5. 12         cout << * it << ", ";
   
6. 13     cout << endl;
   
7. 14 }           
   
8. 15         
   
9. 16 void t(int n)
   
10. 17 {           
    
11. 18     int k;  
    
12. 19         
    
13. 20     vector<int> s;
    
14. 21
    
15. 22     for(k=0; k<n; k++)
    
16. 23         s.push_back(k);
    
17. 24
    
18. 25     while(!s.empty())
    
19. 26     {
    
20. 27         print_stack(s);
    
21. 28
    
22. 29         int x = s[s.size()-1];
    
23. 30         s.pop_back();
    
24. 31
    
25. 32         while(s.size() < n && !( s.empty() && x == 9))
    
26. 33         {
    
27. 34             if(x < 9)
    
28. 35                 s.push_back(++x);
    
29. 36             else
    
30. 37             {
    
31. 38                 x = s[s.size()-1];
    
32. 39                 s.pop_back();
    
33. 40             }
    
34. 41         }
    
35. 42
    
36. 43     }
    
37. 44 }

复制代码

其中第32条的循环条件有点tricky