技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 1082|回复: 5
收起左侧

【C++】排列生成算法

[复制链接]

11

主题

22

帖子

353

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
202 个
贡献
30 次
宅之契约
0 份
在线时间
13 小时
注册时间
2020-9-26
发表于 2021-3-22 20:11:23 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

x
本帖最后由 usr 于 2021-3-23 13:11 编辑

这篇帖子主要介绍一种排列生成算法,这种算法不同于C++ STL库中的排列生成算法。
读者可以自行分析它的效率。
[C++] 纯文本查看 复制代码
#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[i].direction == CIntPair<T>::LEFT)
            {
                if (i > 0 && arr[i - 1].value < arr[i].value && r.pair.value < arr[i].value)
                {
                    r.pair = arr[i];
                    r.index = i;
                    r.found = true;
                }
            }
            else
            {
                if (i < n - 1 && arr[i + 1].value < arr[i].value && r.pair.value < arr[i].value)
                {
                    r.pair = arr[i];
                    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[i].direction == CIntPair<T>::LEFT)
            swap(arr[i], arr[i - 1]);
        else
            swap(arr[i], arr[i + 1]);
    }
    // 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[i].value > r.pair.value)
                arr[i].direction = !arr[i].direction;
    }
public:
    CArrangement(size_t k) : n(k)
    {
        size_t i;
        arr = new CIntPair<T>[n];
        for (i = 0; i < n; ++i)
        {
            arr[i].direction = CIntPair<T>::LEFT;
            arr[i].value = i + 1;
        }
    }
    CArrangement(const T & initial, size_t k) : n(k)
    {
        size_t i;
        arr = new CIntPair<T>[n];
        for (i = 0; i < n; ++i)
        {
            arr[i].direction = CIntPair<T>::LEFT;
            arr[i].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[i].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类型的数据:
[C++] 纯文本查看 复制代码
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

评分

参与人数 1宅币 +5 收起 理由
0xAA55 + 5 类嵌套类可还行

查看全部评分

回复

使用道具 举报

29

主题

331

帖子

2004

积分

用户组: 上·技术宅

UID
3808
精华
11
威望
105 点
宅币
1243 个
贡献
165 次
宅之契约
0 份
在线时间
379 小时
注册时间
2018-5-6
发表于 2021-3-22 20:57:17 | 显示全部楼层
这算法,真“一波三折”啊!牛
Passion Coding!

11

主题

22

帖子

353

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
202 个
贡献
30 次
宅之契约
0 份
在线时间
13 小时
注册时间
2020-9-26
 楼主| 发表于 2021-3-23 08:42:44 | 显示全部楼层
watermelon 发表于 2021-3-22 20:57
这算法,真“一波三折”啊!牛

再发一种比较直观的排列生成算法。
下面这种算法是Heap算法:
[C++] 纯文本查看 复制代码
#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[0];
	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

11

主题

22

帖子

353

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
202 个
贡献
30 次
宅之契约
0 份
在线时间
13 小时
注册时间
2020-9-26
 楼主| 发表于 2021-3-23 08:48:57 | 显示全部楼层
本帖最后由 usr 于 2021-3-23 13:16 编辑

此处补上STL中的排列生成算法:
[C++] 纯文本查看 复制代码
#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[0];
    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$$

1088

主题

2606

帖子

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
236
威望
474 点
宅币
21372 个
贡献
45937 次
宅之契约
0 份
在线时间
2060 小时
注册时间
2014-1-26
发表于 2021-3-23 12:38:23 | 显示全部楼层
有注释就好了

11

主题

22

帖子

353

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
202 个
贡献
30 次
宅之契约
0 份
在线时间
13 小时
注册时间
2020-9-26
 楼主| 发表于 2021-3-23 12:43:41 | 显示全部楼层

感谢反馈,抽时间添加。

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2021-10-29 05:03 , Processed in 0.042820 second(s), 30 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表