全排列问题算法及实现（Permutation）

本文主要是介绍全排列问题算法及实现（Permutation），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

做项目遇到数据采集系统中ADC拼合问题，如果顺序不对，波形就是错误的（题外话），为了找到正确的顺序，涉及到排列问题。

什么是排列组合

定义

一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(Arrangement)。特别地，当m=n时，这个排列被称作全排列(Permutation)。
Ex：考虑三个数字1,2,3，这个序列有6个可能的排列组合
123
132
213
231
312
321
这些排列组合根据less-than操作符做字典顺序的排序。
字典顺序顾名思义是就是将1-n的一个排列看成一个数，然后按照字典的顺序从小到达的输出

全排列及序号

所谓的全排列，就是说将数字进行不重复的排列，所有得到的序列，就是全排列
给定数字1 ， 2 ， 3 ， 4，其全排列是：
{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}
全排列如上所示，那么什么是全排列的序号？这里我们通常将全排列按照字典序进行编排，就如上面从左到右看，就是按照字典序排列的。
我们说，对于1,2,3,4的全排列，第20号序列是{4,1,3,2}，因为其在这个按照字典序排列的全排列中处在第20的位置。