产生一个数组的全排列,非冗余 C++实现

浏览数：27 / 时间：2015年06月08日

finds all the permutaitons of n elements, repeated elements are allowed and do not create redundant permutations.

蛋白质组学Ms-TopDown源代码auxfun.cpp中一个函数,看了很久没有注释,有点晕,但是以后可以直接拿来使用.

产生原始数组元素的全排列,但是要求是非冗余的,也就是说原始数组可以有重复的元素,比如{2,2,2}这个数组,只有一种排列,2这个元素必须按相同处理,只是个数是3

 1 void generate_all_permutations(const vector<int>& org_vector, 
 2                                vector< vector<int> >& permutations)
 3 {
 4     unsigned int i;
 5     vector<int> counts, symbols;
 6     permutations.clear();
 7 
 8     if (org_vector.size() == 0)
 9         return;
10 
11     counts.clear();
12     symbols.clear();
13 
14     // create vector with symbols and their counts
15     symbols.push_back(org_vector[0]);
16     counts.push_back(1);
17 
18     for (i=1; i<org_vector.size(); i++)
19     {
20         unsigned int j;
21         for (j=0; j<counts.size(); j++)
22         {
23             if (org_vector[i] == symbols[j])
24             {
25                 counts[j]++;
26                 break;
27             }
28         }
29 
30         if (j == counts.size())
31         {
32             symbols.push_back(org_vector[i]);
33             counts.push_back(1);
34         }
35     }
36 
37     vector<int> next_sym_idx,perm;
38     int n = org_vector.size(); // total number of elements
39     int k = counts.size(); // total number of element types
40     next_sym_idx.resize(n,0);
41     perm.resize(n,-1);
42     int d=0;
43 
44     while (1)
45     {
46         while (next_sym_idx[d]<k && counts[next_sym_idx[d]] == 0)
47             next_sym_idx[d]++;
48 
49         if (next_sym_idx[0]==k)
50             break;
51 
52         if (next_sym_idx[d] >= k)
53         {
54             next_sym_idx[d]=0;
55             d--;
56             counts[next_sym_idx[d]]++;
57             next_sym_idx[d]++;
58             continue;
59         }
60 
61         // add symbol
62         perm[d]=symbols[next_sym_idx[d]];
63         counts[next_sym_idx[d]]--;
64         d++;
65 
66         if (d == n)
67         {
68             permutations.push_back(perm);
69     //        int k;
70     //        for (k=0; k<perm.size(); k++)
71     //            cout << perm[k] << " ";
72     //        cout << endl;
73 
74             d--;
75             counts[next_sym_idx[d]]++;
76             next_sym_idx[d]++;
77         }
78     }
79 }