【C++】排列生成算法
本帖最后由 usr 于 2021-3-23 13:11 编辑这篇帖子主要介绍一种排列生成算法，这种算法不同于C++ STL库中的排列生成算法。
读者可以自行分析它的效率。
#include <iostream>
#include <algorithm>
using namespace std;
template <class T>
class CIntPair
{
public:
static constexpr bool LEFT = false;
static constexpr bool RIGHT = true;
bool direction = LEFT;
T value = 0;
};
template <class T>
class CArrangement
{
private:
class CRtn
{
public:
bool found;
CIntPair<T> pair;
size_t index;
CRtn(size_t i, CIntPair<T> & p) : pair(p), index(i), found(false) {}
};
size_t n;
unsigned long long counter = 1;
CIntPair<T> * arr;
// Function: MaxMovableIndex
// Description:
// A number(CIntPair) is movable, only if the adjacent number that the direction of the movable number pointed is less than
// the removable number.
// Therefor this procedure is to find the maximum number of all removable numbers.
// If there were the maximun number exist, permutation would be able to go on, otherwise there wouldn't be the next permuatation.
// And CRtn().found shows whether we could find the max movable number.
// Simultaneously, CRtn().index stores the index of removable number, CRtn().pair stores the movable number itself then.
CRtn MaxMovableIndex()
{
size_t i;
CIntPair<T> t;
CRtn r(0, t);
for (i = 0; i < n; ++i)
{
if (arr.direction == CIntPair<T>::LEFT)
{
if (i > 0 && arr.value < arr.value && r.pair.value < arr.value)
{
r.pair = arr;
r.index = i;
r.found = true;
}
}
else
{
if (i < n - 1 && arr.value < arr.value && r.pair.value < arr.value)
{
r.pair = arr;
r.index = i;
r.found = true;
}
}
}
return r;
}
// Function: Swap
// Description: Swap two adjacent numbers by index and direction.
void Swap(size_t i)
{
if (arr.direction == CIntPair<T>::LEFT)
swap(arr, arr);
else
swap(arr, arr);
}
// Function: ChangeDirection
// Description: Change all directions which belong to p, such that p > r.pair.value.
void ChangeDirection(CRtn & r)
{
size_t i;
for (i = 0; i < n; ++i)
if (arr.value > r.pair.value)
arr.direction = !arr.direction;
}
public:
CArrangement(size_t k) : n(k)
{
size_t i;
arr = new CIntPair<T>;
for (i = 0; i < n; ++i)
{
arr.direction = CIntPair<T>::LEFT;
arr.value = i + 1;
}
}
CArrangement(const T & initial, size_t k) : n(k)
{
size_t i;
arr = new CIntPair<T>;
for (i = 0; i < n; ++i)
{
arr.direction = CIntPair<T>::LEFT;
arr.value = static_cast<T>(i + initial);
}
}
~CArrangement()
{
delete[] arr;
n = 0;
}
bool Permute()
{
if (n <= 1)
return false;
// 1st. find the maximun movable number in arr list as r.
CRtn r = MaxMovableIndex();
if (r.found)
{
// 2nd. Swap r with the number adjacent to r.
Swap(r.index);
// 3rd. Change all directions of p, such that p > r.pair.value.
ChangeDirection(r);
++counter;
}
return r.found;
}
template <class TX>
friend ostream & operator << (ostream & o, const CArrangement<TX> & ra);
};
template <class T>
ostream & operator << (ostream & o, const CArrangement<T> & ra)
{
size_t i;
o << ra.counter << ":\t";
for (i = 0; i < ra.n; ++i)
o << ra.arr.value << " ";
return o;
}
int main(void)
{
CArrangement<int> a(4);
cout << a << endl;
while (a.Permute())
cout << a << endl;
return 0;
}
以上代码执行结果如下：
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类型的数据：
int main(void)
{
CArrangement<char> a('A', 3);
cout << a << endl;
while (a.Permute())
cout << a << endl;
return 0;
}
结果如下：
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 发表于 2021-3-22 20:57
这算法，真“一波三折”啊！牛
再发一种比较直观的排列生成算法。
下面这种算法是Heap算法：
#include <iostream>
#include <algorithm>
using namespace std;
template <class BidirectionalIterator>
void HeapPermutation(BidirectionalIterator first, size_t size, size_t n)
{
if (1 == size)
{
BidirectionalIterator i = first;
size_t j;
for (j = 0; j < n; ++j)
cout << *(i + j) << " ";
cout << endl;
}
else
{
size_t i;
for (i = 0; i < size; ++i)
{
HeapPermutation(first, size - 1, n);
if (size & 0x1)
iter_swap(first, first + size - 1);
else
iter_swap(first + i, first + size - 1);
}
}
}
int main(void)
{
int a[] = { 1,2,3,4 };
int n = sizeof a / sizeof a;
HeapPermutation(a, n, n);
return 0;
}
结果如下：
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 于 2021-3-23 13:16 编辑
此处补上STL中的排列生成算法：
#include <iostream>
#include <algorithm>
using namespace std;
template <class BidirectionalIterator>
bool stl_next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
--i;
for (;;) {
BidirectionalIterator ii = i--;
if (*i < *ii) {
BidirectionalIterator j = last;
while (!(*i < *--j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
int main(void)
{
int a[] = { 1,2,3,4 };
int n = sizeof a / sizeof a;
do
{
for (auto i : a)
cout << i << " ";
cout << endl;
} while (stl_next_permutation(a, a + n));
return 0;
}
运行结果如下（读者可以自行比较以上排列算法生成排列的不同）：
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 发表于 2021-3-23 12:38
有注释就好了
感谢反馈，抽时间添加。
页:
[1]