n元字典序全排列与行列式定义公式 - Vam Works

n元字典序全排列. 在我不了解任何算法的前提下，让我写出3个数的全排列，我会凭直觉写下：. VamWorks I'mslow,prettyslow. Home Contents About PoweredbyHugoTemplatebyBootstrapious.comHugothemebyKishanB©2020VamWorks. Menu VamWorks n元字典序全排列与行列式定义公式 WrittenbyVam;Tuesday,Nov9,2021 行列式相关内容参看丘维声《高等代数》   n元字典序全排列 在我不了解任何算法的前提下，让我写出3个数的全排列，我会凭直觉写下： 123 132 213 231 312 321   4个数的全排列会多一些，但写出来也不费太大力气： 123412431324134214231432 213421432314234124132431 312431423214324134123421 412341324213423143124321   分析思路： 如果串只有1个元素，那么它只有1种排列：没有可以移动的元素 如果串有2个元素，那么它有2种排列：12与21 如果串有3个元素，从最右侧开始，先把-1位置的元素移动到-2位置，到这里相当于完成了2元情况下的所有排列； 继续向左侧找，发现-3位置还有元素，那么把-2位置的元素移动到-3位置； 在上一步的基础上，再把-1位置的元素移动到-2位置； …… 元素:1234 -------- 位置:-4-3-2-1 如果串是“1234”，把-1位置的元素移动到-3位置，不动的元素自动被挤到后面去，得到“1423”。

把排列的流程继续画图做深入的分析： 从上图能看出写出排列时的规律，如果把结果换成一个移动位置的函数move(origin,target)，可以得到下图： 从上图可以看出一个明显的递归结构：先做2级的任务，发现有3级，要把它包含的2级的任务都做了，发现有4级，也要做3级、2级的任务……以此类推。

到这里就可以开始设计算法，但又发现一个问题，不论串是几元，都从最右侧开始移动，每当升到高一级，就又会从2元开始，造成图上有空缺的地方。

这些地方如果写条件判断，会比较麻烦；那么换个角度，我能否补上一些操作？于是得到下图： 上图中灰色的操作是补全的，会发现它其实就是高阶坐标的位置与自己交换。

反过来想，我如果把一个1元串做全排列，它的结果只有一个，就是它自己，它的移动过程就是move(-1,-1)，也就等于什么都没做。

也就是说1元串的全排列操作只有一次，我如果把1元串的全排列操作应用在任意长度的串上，这个串就是它自己。

补全以后，递归的逻辑简单了，但问题是会产生重复；解决重复的问题很简单，因为有一个很明显的条件可以判断–origin位置与target相等。

到此逻辑清晰了，规则可以推广到n元，写代码：   行列式定义公式 很多教程都以3级行列式为范例： $\begin{vmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\\ \end{vmatrix}$ $=a_{11}a_{22}a_{33}+a_{12}a_{23}a_{31}+a_{13}a_{21}a_{32}-a_{13}a_{22}a_{31}-a_{12}a_{21}a_{33}-a_{11}a_{23}a_{32}$ 上面这张图，在视觉上对我有一定的误导性。

3阶行列式的排列组合方法是先从左向右划斜线，再从右向左画斜线；如果4阶行列式也这样操作就不对了，因为n阶行列式的项的数量是n!个，也就是n的全排列的数量。

回到行列式的定义： n阶行列式是n!的代数和，其中每一项是位于不同行、不同列的n个元素的乘积，把这n个元素以行指标为自然序列排好位置，当列指标构成的排列是偶排列时，该项带正号；是奇排列时，该项带负号。

$\begin{vmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{21}&\cdots&a_{2n}\\ \vdots&\vdots&\vdots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn} \end{vmatrix}=\displaystyle\sum_{j_1j_2\cdotsj_n}(-1)^{\tau(j_1j_2\cdotsj_n)}a_{1j_1}a_{2j_2}\cdotsa_{nj_n}$ 不考虑符号，先去考虑排列组合的问题，定义中的关键词是”……不同行、不同列的n个元素……” 现在我有一个4阶行列式，我开始写它的第一项，选取第一个元素，这时每个元素我都可以选择： 当我选定第一个元素是a11；开始选第2个元素，由于定义中要求“……不同行、不同列……”，那么a11所在的行与列就都不能成为第2个元素所选择的范围，第2个元素的可选范围是绿色部分： 这也是为什么要“划掉a11的所在行与所在列……”；同理选择第二个元素为a22之后，可选范围如下： 到这里也可以理解什么叫做“行列式按行（列）展开”。

就是一行（列）中的每一个元素带领下的排列组合。

接下来画出4阶行列式所有的排列组合： 观察上图，发现了重要规律：4阶行列式的项的排列组合，它的列指标的变化就是4元串的全排列，而它的行指标是从1到4的循环，所以项数一共是4的阶乘个，即全排列的数量；行指标全都是顺序，不用考虑，列指标的逆序数决定了该项的符号。

有了这个规律，豁然开朗，开始写代码： 更改代码第7行变量det_order的值，就可以看到高阶行列式的视觉形式了。

ThisworkislicensedunderaCreativeCommonsAttribution4.0InternationalLicense. 2018VamWorks.Allrightsreserved.