C++代码示例：排列数简单生成工具

前言

C++代码示例：排列数简单生成工具。

---

代码仓库

• yezhening/Programming-examples: 编程实例 (github.com)
• Programming-examples: 编程实例 (gitee.com)

---

内容

• 简单地生成排列数
• 有详细的步骤解析

---

代码（有详细注释）

cpermutation.cpp

#include 
#include 
#include 

using std::cout;
using std::endl;
using std::unordered_set;
using std::vector;

class CPermutation
{
public:
    CPermutation(const int &n, const int &m) : n(n), m(m), flags(0), curPerm(0), permCount(0) {}

    bool next()
    {
        // 第一次进入初始化当前排列，如m=3，this->curPerm为012，从012开始遍历
        if (this->curPerm.empty() == true)
        {
            for (int i = 0; i < this->m; ++i)
            {
                this->curPerm.push_back(i);
                this->flags.insert(i); // 记录哈希
            }

            ++this->permCount;
            return true;
        }

        // 1. 首先，确定某个位置是否已经达到了当前意义下的“最大值”—“当前” 的意义：前面的位置数值固定之后
        // 求当前位置应当的最大值
        // 注意理解：如014，索引2位置可取23，最大值为3；索引1位置可取234，最大值为4；索引0位置可取1234，最大值为4，左边位置的取值范围要包括右边的位置
        // 从后往前大到小遍历，如果这个数不在哈希表中就是应该的最大值

        // 2. 然后，从后向前寻找第一个不是当前最大值的位置
        // 修正：小于当前应当最大值的位置
        // 如014，则求得的位置是索引1
        int curPos = this->m - 1;
        int curMax = 0;
        while (curPos >= 0)
        {
            // 1.
            for (int i = this->n - 1; i >= 0; --i)
            {
                if (flags.find(i) == flags.end())
                {
                    curMax = i;
                    break; // 找到就退出for
                }
            }

            // 2.
            if (this->curPerm.at(curPos) >= curMax) // 未找到位置移动
            {
                flags.erase(this->curPerm.at(curPos)); // 哈希表减少
                --curPos;
            }
            else // 找到位置退出while
            {
                break;
            }
        }

        if (curPos < 0) // 没找到位置搜完排列
        {
            return false;
        }

        // 3.这个位置上的数值最小限度地增加—“最小限度”，前面的数值排除之后，取剩余的、大于该值的最小值
        // 从前往后小到大遍历，如果这个数不在哈希表中就是应该变换的值
        // 注意：此时可能处理左边的位置，哈希表还是删减状态以让左边位置可以取到右边的值
        // 如014，遍历012到2最小且不在哈希表，将索引1位置元素1换成2，该位置后续可以取到右边的值4，右边的值相应的会减小不再是4保证不重复
        for (int i = this->curPerm.at(curPos); i < this->n; ++i)
        {
            if (flags.find(i) == flags.end())
            {
                this->flags.erase(this->curPerm.at(curPos)); // 哈希删除
                this->curPerm.at(curPos) = i;
                this->flags.insert(i); // 哈希插入
                break;
            }
        }

        // 归位哈希表。因为右边的数要填充了
        // 如034，位置1可以取到4，但此时哈希表是没有4的，将3变为4后，需要加入哈希表，右边的值填充时不能再是4，不是044而是041
        for (const int p : this->curPerm)
        {
            flags.insert(p);
        }

        // 4. 该位置确定后，后面的位置依次取剩余数值的最小几个
        // 对右边的所有位置
        // 从前往后小到大遍历，如果这个数不在哈希表中就是应该变换的值
        // 如024，遍历01到1最小且不在哈希表，
        for (int i = curPos + 1; i < this->m; ++i)
        {
            for (int j = 0; j < this->n; ++j)
            {
                if (flags.find(j) == flags.end())
                {
                    this->flags.erase(this->curPerm.at(i)); // 哈希删除
                    this->curPerm.at(i) = j;
                    this->flags.insert(j); // 哈希插入
                    break;
                }
            }
        }

        ++this->permCount;
        return true;
    }

    inline void printCurPerm()
    {
        for (const int p : this->curPerm)
        {
            cout << p << " ";
        }
        cout << endl;
    }

    inline void printPermCount()
    {
        cout << this->permCount << endl;
    }

private:
    const int n; // 从n个取m个
    const int m;

    vector<int> curPerm;      // 当前排列，存储排列的索引
    unordered_set<int> flags; // 哈希标志，标记已在排列中的索引
    int permCount;            // 排列数的数量
};

int main()
{
    const int n = 5;
    const int m = 3;
    CPermutation perm(n, m);

    while (perm.next())
    {
        perm.printCurPerm();
    }
    perm.printPermCount();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

---

编译和运行命令

g++ -o cpermutation cpermutation.cpp
./cpermutation.exe
1
2

---

结果

---

总结

C++代码示例：排列数简单生成工具。

---

参考资料

• 学校《高级算法设计与分析》课程课件的算法思路

---

作者的话

• 感谢参考资料的作者/博主
• 作者：夜悊
• 版权所有，转载请注明出处，谢谢~
• 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
• 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
• 文章在认识上有错误的地方, 敬请批评指正
• 望读者们都能有所收获

---