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

顾得泉：个人主页

个人专栏：《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;
}

---

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