【C++】排列生成算法

usr

这篇帖子主要介绍一种排列生成算法，这种算法不同于C++ STL库中的排列生成算法。
读者可以自行分析它的效率。

1. #include <iostream>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. template <class T>
   
6. class CIntPair
   
7. {
   
8. public:
   
9.     static constexpr bool LEFT = false;
   
10.     static constexpr bool RIGHT = true;
    
11.     bool direction = LEFT;
    
12.     T value = 0;
    
13. };
    
14. 
    
15. template <class T>
    
16. class CArrangement
    
17. {
    
18. private:
    
19.     class CRtn
    
20.     {
    
21.     public:
    
22.         bool found;
    
23.         CIntPair<T> pair;
    
24.         size_t index;
    
25.         CRtn(size_t i, CIntPair<T> & p) : pair(p), index(i), found(false) {}
    
26.     };
    
27.     size_t n;
    
28.     unsigned long long counter = 1;
    
29.     CIntPair<T> * arr;
    
30.     // Function: MaxMovableIndex
    
31.     // Description:
    
32.     //     A number(CIntPair) is movable, only if the adjacent number that the direction of the movable number pointed is less than
    
33.     //     the removable number.
    
34.     //     Therefor this procedure is to find the maximum number of all removable numbers.
    
35.     //     If there were the maximun number exist, permutation would be able to go on, otherwise there wouldn't be the next permuatation.
    
36.     //     And CRtn().found shows whether we could find the max movable number.
    
37.     //     Simultaneously, CRtn().index stores the index of removable number, CRtn().pair stores the movable number itself then.
    
38.     CRtn MaxMovableIndex()
    
39.     {
    
40.         size_t i;
    
41.         CIntPair<T> t;
    
42.         CRtn r(0, t);
    
43.         for (i = 0; i < n; ++i)
    
44.         {
    
45.             if (arr[i].direction == CIntPair<T>::LEFT)
    
46.             {
    
47.                 if (i > 0 && arr[i - 1].value < arr[i].value && r.pair.value < arr[i].value)
    
48.                 {
    
49.                     r.pair = arr[i];
    
50.                     r.index = i;
    
51.                     r.found = true;
    
52.                 }
    
53.             }
    
54.             else
    
55.             {
    
56.                 if (i < n - 1 && arr[i + 1].value < arr[i].value && r.pair.value < arr[i].value)
    
57.                 {
    
58.                     r.pair = arr[i];
    
59.                     r.index = i;
    
60.                     r.found = true;
    
61.                 }
    
62.             }
    
63.         }
    
64.         return r;
    
65.     }
    
66.     // Function: Swap
    
67.     // Description: Swap two adjacent numbers by index and direction.
    
68.     void Swap(size_t i)
    
69.     {
    
70.         if (arr[i].direction == CIntPair<T>::LEFT)
    
71.             swap(arr[i], arr[i - 1]);
    
72.         else
    
73.             swap(arr[i], arr[i + 1]);
    
74.     }
    
75.     // Function: ChangeDirection
    
76.     // Description: Change all directions which belong to p, such that p > r.pair.value.
    
77.     void ChangeDirection(CRtn & r)
    
78.     {
    
79.         size_t i;
    
80.         for (i = 0; i < n; ++i)
    
81.             if (arr[i].value > r.pair.value)
    
82.                 arr[i].direction = !arr[i].direction;
    
83.     }
    
84. public:
    
85.     CArrangement(size_t k) : n(k)
    
86.     {
    
87.         size_t i;
    
88.         arr = new CIntPair<T>[n];
    
89.         for (i = 0; i < n; ++i)
    
90.         {
    
91.             arr[i].direction = CIntPair<T>::LEFT;
    
92.             arr[i].value = i + 1;
    
93.         }
    
94.     }
    
95.     CArrangement(const T & initial, size_t k) : n(k)
    
96.     {
    
97.         size_t i;
    
98.         arr = new CIntPair<T>[n];
    
99.         for (i = 0; i < n; ++i)
    
100.         {
     
101.             arr[i].direction = CIntPair<T>::LEFT;
     
102.             arr[i].value = static_cast<T>(i + initial);
     
103.         }
     
104.     }
     
105.     ~CArrangement()
     
106.     {
     
107.         delete[] arr;
     
108.         n = 0;
     
109.     }
     
110.     bool Permute()
     
111.     {
     
112.         if (n <= 1)
     
113.             return false;
     
114.         // 1st. find the maximun movable number in arr list as r.
     
115.         CRtn r = MaxMovableIndex();
     
116.         if (r.found)
     
117.         {
     
118.             // 2nd. Swap r with the number adjacent to r.
     
119.             Swap(r.index);
     
120.             // 3rd. Change all directions of p, such that p > r.pair.value.
     
121.             ChangeDirection(r);
     
122.             ++counter;
     
123.         }
     
124.         return r.found;
     
125.     }
     
126.     template <class TX>
     
127.     friend ostream & operator << (ostream & o, const CArrangement<TX> & ra);
     
128. };
     
129. 
     
130. template <class T>
     
131. ostream & operator << (ostream & o, const CArrangement<T> & ra)
     
132. {
     
133.     size_t i;
     
134.     o << ra.counter << ":\t";
     
135.     for (i = 0; i < ra.n; ++i)
     
136.         o << ra.arr[i].value << " ";
     
137.     return o;
     
138. }
     
139. 
     
140. int main(void)
     
141. {
     
142.     CArrangement<int> a(4);
     
143.     cout << a << endl;
     
144.     while (a.Permute())
     
145.         cout << a << endl;
     
146.     return 0;
     
147. }
     

复制代码

以上代码执行结果如下：
1:      1 2 3 4
2:      1 2 4 3
3:      1 4 2 3
4:      4 1 2 3
5:      4 1 3 2
6:      1 4 3 2
7:      1 3 4 2
8:      1 3 2 4
9:      3 1 2 4
10:     3 1 4 2
11:     3 4 1 2
12:     4 3 1 2
13:     4 3 2 1
14:     3 4 2 1
15:     3 2 4 1
16:     3 2 1 4
17:     2 3 1 4
18:     2 3 4 1
19:     2 4 3 1
20:     4 2 3 1
21:     4 2 1 3
22:     2 4 1 3
23:     2 1 4 3
24:     2 1 3 4
本算法来自：Richard A. Brualdi Introductory Combinatorics, Fifth Edition
以上源代码已经经过了修改。引入模板类，目的是为了能像STL的函数一样对任意整数类型进行排列。
这样就能排列char类型的数据：

1. 
   
2. int main(void)
   
3. {
   
4.     CArrangement<char> a('A', 3);
   
5.     cout << a << endl;
   
6.     while (a.Permute())
   
7.         cout << a << endl;
   
8.     return 0;
   
9. }

复制代码

结果如下：
1:      A B C
2:      A C B
3:      C A B
4:      C B A
5:      B C A
6:      B A C

watermelon

这算法，真“一波三折”啊！牛

usr

watermelon 发表于 2021-3-22 20:57
这算法，真“一波三折”啊！牛

再发一种比较直观的排列生成算法。
下面这种算法是Heap算法：

1. #include <iostream>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. template <class BidirectionalIterator>
   
6. void HeapPermutation(BidirectionalIterator first, size_t size, size_t n)
   
7. {
   
8.         if (1 == size)
   
9.         {
   
10.                 BidirectionalIterator i = first;
    
11.                 size_t j;
    
12.                 for (j = 0; j < n; ++j)
    
13.                         cout << *(i + j) << " ";
    
14.                 cout << endl;
    
15.         }
    
16.         else
    
17.         {
    
18.                 size_t i;
    
19.                 for (i = 0; i < size; ++i)
    
20.                 {
    
21.                         HeapPermutation(first, size - 1, n);
    
22.                         if (size & 0x1)
    
23.                                 iter_swap(first, first + size - 1);
    
24.                         else
    
25.                                 iter_swap(first + i, first + size - 1);
    
26.                 }
    
27.         }
    
28. }
    
29. 
    
30. int main(void)
    
31. {
    
32.         int a[] = { 1,2,3,4 };
    
33.         int n = sizeof a / sizeof a[0];
    
34.         HeapPermutation(a, n, n);
    
35.         return 0;
    
36. }
    

复制代码

结果如下：
1 2 3 4
2 1 3 4
3 1 2 4
1 3 2 4
2 3 1 4
3 2 1 4
4 2 3 1
2 4 3 1
3 4 2 1
4 3 2 1
2 3 4 1
3 2 4 1
4 1 3 2
1 4 3 2
3 4 1 2
4 3 1 2
1 3 4 2
3 1 4 2
4 1 2 3
1 4 2 3
2 4 1 3
4 2 1 3
1 2 4 3
2 1 4 3

usr

此处补上STL中的排列生成算法：

1. #include <iostream>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. template <class BidirectionalIterator>
   
6. bool stl_next_permutation(BidirectionalIterator first,
   
7.     BidirectionalIterator last) {
   
8.     if (first == last) return false;
   
9.     BidirectionalIterator i = first;
   
10.     ++i;
    
11.     if (i == last) return false;
    
12.     i = last;
    
13.     --i;
    
14. 
    
15.     for (;;) {
    
16.         BidirectionalIterator ii = i--;
    
17.         if (*i < *ii) {
    
18.             BidirectionalIterator j = last;
    
19.             while (!(*i < *--j));
    
20.             iter_swap(i, j);
    
21.             reverse(ii, last);
    
22.             return true;
    
23.         }
    
24.         if (i == first) {
    
25.             reverse(first, last);
    
26.             return false;
    
27.         }
    
28.     }
    
29. }
    
30. 
    
31. int main(void)
    
32. {
    
33.         int a[] = { 1,2,3,4 };
    
34.         int n = sizeof a / sizeof a[0];
    
35.     do
    
36.     {
    
37.         for (auto i : a)
    
38.             cout << i << " ";
    
39.         cout << endl;
    
40.     } while (stl_next_permutation(a, a + n));
    
41.         return 0;
    
42. }
    

复制代码

运行结果如下（读者可以自行比较以上排列算法生成排列的不同）：
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
当然，SV库中的算法就是STL的算法：【C】计算排列组合
下面给出Stirling公式，该公式用于估算n!的大小：
$$P_n^n = n!$$
$$n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

0xAA55

有注释就好了

usr

0xAA55 发表于 2021-3-23 12:38
有注释就好了

感谢反馈，抽时间添加。