一道排列题的做法讨论
题目大概是这样的：定义desirable数：如果一个数的每一位都严格升序，则该数为desirable数。
如：123, 489, 2678
某人使用了一个desirable数做密码。现在你被告称这个密码的长度为N位，
请用程序排列出所有的可能性。
二楼开始讨论实现方法。 显然这是一道10选N的排列问题。最简单的做法就是用递归函数来实现。
这个递归函数的定义大概是这样：
列出desirable数：起始于b, 共n位
相当于：
* 列出第一位数 <1>
* 在余下的数中做list_desirable(k+1, n-1)，这里k为上面列出来的数的值
对于<1>，直觉上我会列出b:9的所有数，但事实上只需要写出 b : 9 - n + 1 这些数则可。
由于程序需要打印所有的排列，所以需要一个数据结构来记录现在已经列出来的数。
我们知道，当递归前进一步时，这个记录添加一个数；递归完成一步后，这个记录会减少一个数，
是明显的LIFO结构，所以用堆栈来实现
于是pseudo-code可以这样写：ADT list_stack {
V[] {记录已经入栈的数}
top : integer
push(int x);
pop();
as_string() : string;
is_empty() : boolean
}
list_desirable(list_stack, int begin, int num)
{
for(k = begin : 9 - num + 1)
{
list_stack.push(k);
if(num==1)
print(list_stack);
else
list_desirable(list_stack, k+1, num-1);
list_stack.pop();
}
再看非递归的实现方法
代码很短，直接贴代码好了。由于C++中的stack不支持遍历，只好用vector来做栈（其实应该用list）8 template<class T> void print_stack(vector<T> &s)9 {
10 typename vector<T>::iterator it;
11 for(it=s.begin(); it!=s.end(); it++)
12 cout << * it << ", ";
13 cout << endl;
14 }
15
16 void t(int n)
17 {
18 int k;
19
20 vector<int> s;
21
22 for(k=0; k<n; k++)
23 s.push_back(k);
24
25 while(!s.empty())
26 {
27 print_stack(s);
28
29 int x = s;
30 s.pop_back();
31
32 while(s.size() < n && !( s.empty() && x == 9))
33 {
34 if(x < 9)
35 s.push_back(++x);
36 else
37 {
38 x = s;
39 s.pop_back();
40 }
41 }
42
43 }
44 }其中第32条的循环条件有点tricky
页:
[1]