一篇文章带你搞懂---全排序

顾得泉：个人主页

个人专栏：《Linux操作系统》  《C/C++》  《LeedCode刷题》

键盘敲烂，年薪百万！

---

       全排序（Permutation）是指将一组元素按照一定的顺序进行排列的过程。在计算机科学中，全排序是一个经典的问题，常用于解决排列组合、搜索和优化等领域的算法设计。

       具体来说，全排序是指对于给定的n个元素，将它们按照不同的顺序进行排列，得到所有可能的排列结果。例如，对于3个元素{1, 2, 3}，全排序的结果为{1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 1, 2}、{3, 2, 1}共6种排列方式。

一、C语言基础实现

在C语言中，可以使用递归的方式来实现全排列。具体步骤如下：

1. 定义一个递归函数，接受一个数组和两个整数作为参数。其中，数组存储待排列的元素，第一个整数表示当前排列的起始位置，第二个整数表示当前排列的结束位置。
2. 当起始位置等于结束位置时，表示已经完成了一种排列，可以将当前排列输出。
3. 从起始位置开始，依次将每个元素与起始位置交换，并递归调用函数，将起始位置后移一位。
4. 在递归调用结束后，需要将交换过的元素还原回原来的位置，以便进行下一次交换。
5. 重复步骤3和步骤4，直到起始位置等于结束位置。

以下是使用递归方式实现全排序的示例代码：

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) 
{int temp = *a;*a = *b;*b = temp;
}// 全排序递归函数
void permute(int* arr, int start, int end) 
{if (start == end) {// 打印当前排列结果for (int i = 0; i <= end; i++) {printf("%d ", arr[i]);}printf("\n");}else {for (int i = start; i <= end; i++) {// 交换第start个元素与第i个元素swap(&arr[start], &arr[i]);// 递归生成下一层排列permute(arr, start + 1, end);// 恢复交换前的状态，以便进行下一次交换swap(&arr[start], &arr[i]);}}
}int main() 
{int arr[] = { 1, 2, 3 };int n = sizeof(arr) / sizeof(arr[0]);printf("全排序结果：\n");permute(arr, 0, n - 1);return 0;
}

       运行以上代码，将会输出全排序的结果：

---

二、调用库函数实现 

       还有一种更便捷的实现方式就是使用C语言中的库函数next_permutation，以下我用c++进行库函数使用代码展示：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {vector<int> nums = { 1, 2, 3 };// 对nums进行全排列cout << "全排序结果：" << endl;do {for (int num : nums) {cout << num << " ";}cout << endl;} while (next_permutation(nums.begin(), nums.end()));return 0;
}

 运行以上代码，将会输出全排序的结果：

       对比来说，调用库函数结果相同，并且对我们来说更容易实现相应操作，所以大家赶快练起来。

---

三、实战演练

题目描述

       人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

       火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 1,2,3,⋯1,2,3,⋯。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

       一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 1,2,3,41,2,3,4 和 55，当它们按正常顺序排列时，形成了 55 位数 1234512345，当你交换无名指和小指的位置时，会形成 55 位数 1235412354，当你把五个手指的顺序完全颠倒时，会形成 5432154321，在所有能够形成的 120120 个 55 位数中，1234512345 最小，它表示 11；1235412354 第二小，它表示 22；5432154321 最大，它表示 120120。下表展示了只有 33 根手指时能够形成的 66 个 33 位数和它们代表的数字：

三进制数	代表的数字
123123	11
132132	22
213213	33
231231	44
312312	55
321321	66

       现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

        共三行。
        第一行一个正整数 N，表示火星人手指的数目（1≤N≤10000）
        第二行是一个正整数 M，表示要加上去的小整数（1≤M≤100）
        下一行是 1 到 N 这 N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序

输出格式

       N 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

输入输出样例

输入：

输出：

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, arr[10001];
int main()
{cin >> n >> m;for(int i = 1; i <= n; i++)cin >> arr[i];for(int i = 1; i <= m; i++)next_permutation(arr + 1, arr + 1 + n);for(int i = 1; i < n; i++)cout << arr[i] << ' ';cout << arr[n];return 0;
}

---

结语：关于全排序的简单分享到这里就结束了，希望本篇文章的分享会对大家的学习带来些许帮助，如果大家有什么问题，欢迎大家在评论区留言，最后祝大家新的一年里学业有成，天天开心~~~