Zero Lee的专栏

一组数的全排列和组合程序实现

显示一组数的全排列和组合程序：
 1 void print(const std::vector<int>& s)
 2 {
 3     static int n = 1;
 4     printf("%d:", n++);
 5     printf("[");
 6     for (int i = 0; i < s.size(); i++)
 7         printf(" %d ", s[i]);
 8     printf("]\n");
 9 }
10 
11 void permutation(std::vector<int>& v, int beg, int end)
12 {
13     if (beg > end) {
14         print(v);
15         return;
16     }
17     for (int i = beg; i <= end; i++) {
18         std::swap(v[i], v[beg]);
19         permutation(v, beg+1, end); // pleate note, here always beg+1, not i+1
20         std::swap(v[i], v[beg]);
21     }
22 }
23 
24 void pm(std::vector<int>& v)
25 {
26     std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
27     printf("\nfull permulation are:\n");
28     permutation(v, 0, v.size()-1);
29 }
30 
31 void print(const std::vector<int>& v, int beg, int end)
32 {
33     static int n = 1;
34     printf("%d:", n++);
35     printf("[");
36     std::copy(v.begin()+beg, v.begin()+end+1, std::ostream_iterator<int>(std::cout, " "));
37     printf("]\n");
38 }
39 
40 void fullcombination(std::vector<int>& v)
41 {
42     printf("
full combination are:\n");
43     for (unsigned int i = 0; i < v.size(); i++) {
44         print(v, i, i);
45         for (unsigned int j = i+1; j < v.size(); j++) {
46             for (int k = 0; k < v.size()-j; k++) {
47                 std::swap(v[j+k], v[j]);
48                 print(v, i, j);
49                 std::swap(v[j+k], v[j]);
50             }
51         }
52     }
53 }
54 

posted on 2011-10-19 09:34 Zero Lee 阅读(688) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理