对于 1-5 生成它的全排列，这里只列出三个方法：自底向上生成排列（插入）、Johnson-Trotter 算法、字典序算法。但是本人没有考虑到边界问题，所以可能处理边界情况的时候会报错。
自底向上生成排列，说白了就是在一个序列的空隙中插入待排列数据，如果现在只有一个元素，它的全排列就只有一个 {1}。那么它就会有两个位置可以插入 2，插入之后就有两个排列，也就是 {2, 1}、{1, 2}，这两个排列都有三个位置可以插入 3。3 个元素的全排列就是 {3, 2, 1}、{2, 3, 1}、{2, 1, 3}、{3, 1, 2}、{1, 3, 2}、{1, 2, 3}。
我们可以借助递归来实现这一算法：
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> result;
vector<int>::iterator it;
void AllSort(int n) {
// 存储待插入元素的排列
vector<int> curr;
for (int i = 1; i < n; i++) {
// 暂时存储本轮的全排列
vector<vector<int>> temp;
// 记录插入的位置
int j = 0;
// 遍历上一轮中的全排列
for (int k = 0; k < result.size(); k++) {
for (int j = 0; j < i + 1; j++) {
// 取出上一轮的全排列
curr = result[k];
// 计算插入位置
it = curr.begin() + j;
// 插入元素
curr.insert(it, i + 1);
// 暂存全排列
temp.push_back(curr);
}
}
result = temp;
}
}
int main() {
// 初始化，先插入仅有一个元素的排列
result.push_back({1});
AllSort(4);
// 输出
for (int n = 0; n < result.size(); n++) {
cout << '{';
for (int m = 0; m < result[n].size(); m++) {
cout << result[n][m];
if (m != result[n].size() - 1)
cout << ',';
}
cout << '}' << endl;
}
return 0;
}JT 算法对于 1-5 数字全排列是这么做的：
这是初始状态，如果说一个元素指向的元素比他小，那么就说这个元素可以移动，找到其中最大的可移动元素 A，移动，直到 A 不能移动再查找序列中比 A 大的元素，反转方向，再次循环。
#include <iostream>
using namespace std;
// 交换元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 判断元素是否能够移动
bool IsMovable(int arr[], int mark[], int index, int n) {
int next = index + mark[index];
// 下标小于 0 或者大于 n 都不能移动
if (next < 0) return false;
if (next > n - 1) return false;
// 如果本元素大于下一个元素，则可以移动
return arr[index] > arr[next];
}
// 反转标记
void RevertMark(int &mark) {
if (mark == -1) mark = 1;
else mark = -1;
}
// 打印数组
void PrintArr(int arr[], int n) {
cout << '{';
for (int i = 0; i < n; i++) {
cout << arr[i];
if (i != n - 1) cout << ',';
}
cout << '}' << endl;
}
void JT(int n) {
// 分配待排序序列空间
int* arr = (int*)malloc(sizeof(int) * n);
// 分配标记空间
int* mark = (int*)malloc(sizeof(int) * n);
// 标记序列中是否还有能够移动的标记
int count = n;
// 初始化待排序序列和标记数组
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
mark[i] = -1;
}
// 最初的状态也是一个排列
PrintArr(arr, n);
while(count>0){
int k = -1, index = -1;
// 计算序列中所有可以移动的元素
for (int i = 0; i < n; i++) {
if (IsMovable(arr, mark, i, n) && arr[i] > k) {
k = arr[i], index = i;
}
}
// 计算元素移动位置
int next = index + mark[index];
// 移动元素
while (IsMovable(arr, mark, index, n)) {
swap(arr[index], arr[next]);
swap(mark[index], mark[next]);
index = next;
next = index + mark[index];
count--;
PrintArr(arr, n);
//PrintArr(mark, n);
}
// 反转所有比这次移动元素大的元素方向并判断是否可以移动
for (int i = 0; i < n; i++) {
if (arr[i] > k) RevertMark(mark[i]);
if (IsMovable(arr, mark, i, n)) count++;
}
}
}
int main() {
JT(3);
return 0;
}先从右往左，找出第一个比右边元素小的元素 A ，再从右往左找到第一个比 A 大的元素 B，交换 A 和 B 之后，A 的下标后移，接着反转从 A 到序列最右边的所有元素，如果有比右边的元素小的元素，则继续下次循环。如：
1234 先找到 3 ，再从右到左找到第一个比 3 大的 4，交换 3 4 得 1243；接着找到 A:2，B:3，交换：1342，反转 1324；接着 A:2，B:4，交换：1342，以此类推，可以得到 1234 这 4 个元素的全排列。
#include <iostream>
using namespace std;
// 交换元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 判断是否可以继续排列，如果有比右边元素小的元素，那么可以继续排列
bool ContinueSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
if (arr[i] < arr[i + 1]) return true;
}
return false;
}
// 打印数组
void PrintArr(int arr[], int n) {
cout << '{';
for (int i = 0; i < n; i++) {
cout << arr[i];
if (i != n - 1) cout << ',';
}
cout << '}' << endl;
}
void ZiDianSort(int arr[], int n) {
int a = 0, b = 0;
while(ContinueSort(arr,n)){
for (int i = n - 1; i > 0; i--) {
// 从右往左找到第一个比右边小的元素
if (arr[i] > arr[i - 1]) {
// 记录该元素的下标 a
a = i - 1;
break;
}
}
// 再从右往左找到第一个比下标 a 元素大的元素
for (int j = n - 1; j > 0; j--) {
if (arr[j] > arr[a]) {
// 记录下标为 b
b = j;
break;
}
}
// 交换两个元素
swap(arr[a], arr[b]);
// a 的下标后移
a++;
b = n-1;
// 反转从 a 到 序列最右边的元素
while (a < b) {
swap(arr[a++], arr[b--]);
}
PrintArr(arr, n);
}
}
int main() {
int n = 4;
int* arr = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
PrintArr(arr, n);
ZiDianSort(arr,n);
return 0;
}本文最后更新于 2023 年 11 月 17 日