字典序全排列算法及逆序数归并排序算法
原本是作为一个附件的 不过考虑到当时在整全排列的时候（那个时候还只是信奥入门）并没有把自己的思路记录下来 而且OneNote那边并没有完善的代码框功能 再加上如今在拥有了更多的见识后也有了一些新的想法 所以最终还是决定在洛谷这里开一个专栏
首先对于全排列 相信每个信奥人都不会陌生 作为信奥的入门级问题 我们一般使用深搜来解决 不过若是只需要输出1~n的字典序 那就太简单了 我们现在来思考一个进阶版本：如何在原版深搜的基础上作出改动来保证输出的每一种排列情况是按照字典序的呢？
所谓字典序 其实很简单 对于一个初始的排列情况 我们对每一个排列的字符打上一个编号 这个编号将会始终跟随着字符 那么对于接下来不同的字符排列情况 每种情况都会对应一个编号数列 编号数列里的编号和当前排列方式下的字符一一对应 我们把这个编号数列取消空格 把它看成一个数字 如果输出的排列情况所对应的编号数列组成的数字按照从小到大来排列 那么我们就称这种输出顺序为字典序 比如1~3全排列 字典序输出就应该是123 132 213 231 312 321
同时从这个例子中 我们不难发现 字典序数小的排列情况往往将小数字排在靠前的位置 而字典序数大的排列情况则是将大数字排在靠前的位置 现在试想又两种排列情况 我们需要比较它们的字典序大小 其实要做的只不过就是从第一位开始 看看当前位置下谁的数字大 如果一样就继续看第二位 再一样 就看第三位…以此类推 这其实就和上文所说的把每种排列情况看成数字 然后依照数字大小排列的逻辑是不谋而合的 无论是比较数字大小还是比较字典序大小 它们根本上都采取这种逐位比较的思想 因此对字典序的两种定义能够统一
那么如何用深搜来实现这个逻辑呢？ 我们不妨设立一个数字库 里面按照从小到大的顺序存入等待排列的1~n个数字 然后我们再设立一个答案数组 用来储存排列情况 接下来我们需要从数字库中挑选数字 填入到答案数组中形成不同的排列情况 由于有n个数字 所以答案数组共有n个空位 允许填入n个数字 数字库的作用就在于记录每个数字是否已经被填入答案数组 要知道全排列中不存在重复数字 我们设定当某个数字在数字库中为true时 说明它并没有被填入过 而如果数字库中为false 那么它就已经被填入了
接下来构思递归部分 试想在每一次调用深搜函数时 我们都设定一个指向数字库中第一个数字1的指针 指针从左到右移动 依次指向从小到大每个数字 当遇到第一个true的数字时 我们就将它填入到答案数组中当前的位置 并把它在数字库中设为false代表它已经被填入过 然后递归进入下一轮函数调用 去讨论加入了这个数字之后答案数组的下一位可以填入哪些数字 会出现哪些排列情况 也就是重复上述的步骤 函数最初应该从答案数组的第一位开始调用 逐步递归到第二位 第三位…第n位 然后开始回溯 按照上面所说的这样来做 我们每一次填入当前位置的数字都是除被调用过数字剩下的最小的数字 那么按照这样法则填出来的排列情况必然是当前可用数字能填出来的字典序最小的排列情况 如果填入当前最小数字的排列情况已经全部讨论完了 我们只需要将指针从左到右移向下一个true的次小的数字 然后又从这个次小的数字开始递归到答案数组的下一位讨论以它为首的排列情况 这样一来 我们所讨论的排列情况的字典序从小 到次小到次次小…最终能够实现所有字典序排列情况的遍历
光有递归部分还不行 在回溯部分 导致回溯的将会有两种原因 第一种 函数的递归调用已经调用到了第n位 此时答案数组已经被填满 同时数字库中也将只剩下一个true的数字 我们要做的就是填入它然后将答案数组输出 然后回溯 第二种情况则是当前答案数组位置所有可能填入的数字全部被填完了 如上文所说 当我们讨论完以某个数字为首的情况后 函数再次回溯到当前答案数组位置 我们就需要移动指针去访问下一个可能填入的次小的数字 如果已经没有数字给我们访问了 那么我们需要做的就是回溯到答案数组的再上一位 然后在上一位改变填入数字解锁全新的排列可能
而不论是第一种原因还是第二种原因 回溯所需要的操作都是一样的 那就是把当前选中放入答案数组的数字移除 让答案数组腾出新得位置以填入新得数字 同时在数字库中把移除的数字设为false 代表它被移除 接下来递归后又可以重新填入
对此 我以1~3的全排列为例 简单演示一下上述逻辑 首先初始情况我们在答案数组第一位填入1 然后递归到答案数组第二位填入目前可用的数字2 3中最小的2 继续递归到答案数组第三位填入最后一个可用的 同时也是最小的数字3 答案数组已满 输出123 移除3回溯到第二位 第二位移除2 指针右移一位填入2以后的次小数字3 然后又递归到答案数组第三位 此时只剩下一个数字2 同时也是最小的（没有别的数字了 上面也是同理) 填入2 答案数组已满 输出132 然后回溯到答案数组第二位 第二位发现指针已经指向数字库中最后一个数字3 无数可选 继续回溯到答案数组第一位 第一位的指针从1移向次小数字2 然后递归到答案数组第二位讨论2开头的其它情况…
在明白了字典序全排列后 我们来看看归并求逆序数的基础 归并排序 同样是信奥入门级的算法 但是它堪称经典 以至于C++中的sort()函数实际上就是使用归并排序作为源代码的(如果你真的像我一样非常无聊 去看sort的源代码的话) 这里稍微回顾一下：
其实所谓归并 讲的就是一个核心思想:大事化小 小事化了 接下来以升序排序为例
对于一个无序数列 我们不断地从数列的中间将它切成两份 重复上述步骤最终把数列切成每份只剩下一个数字 这样分割的过程我们通过递归来实现 每次切成两份各自建立两个子节点 （两次调用函数） 子节点包含分割出来的子数列（数列里包含的数字和原数列对应位置区间中的数字一一对应) 由于每次都是产生两个子节点 最终的递归树将会是一个二叉树 我们从二叉树的叶子节点出发开始回溯 每次都对公用同一个父节点的两个子节点进行一波“擂台赛”
这”擂台赛“就是一种非常朴素的比较方式 对于两个子节点所包含的子数列 我们设定两个指针 初始指向各自的子数列的第一位 我们比较两个指针所指向的数字 把更小的填入到一个临时数组中 然后填入数字的指针右移一位指向下一个数字 重复这样的步骤 每个数字就好像在打擂台一样不断和对方子数列中的数字进行比大小 当比不过的时候就被填入到临时数组中 而当某一个指针指向所在子数列的最后一个数字并且它也已经被填入临时数组 也就是指针无数可指时
我们就将另一个指针所指向的剩下的数字全部按照原顺序填入到临时数组
最后 我们回溯到父节点 然后把临时数组中的数字赋值给父节点对应的子数列作为更新
值得注意的是 上述这些步骤只有在打“擂台赛”的两个子节点所包含的子数列都已经是升序的情况下才成立（要不怎么保证每次填入临时数组的数字都是两个子数列所包含所有数列中最小的呢？） 不过这个条件其实在回溯开始的时候已经被满足了 因为最初的叶子节点由于只有一个数字 本身已经是升序了 而我们不断进行的“擂台赛”在本质上就是保证将两个升序子数列合并成一个更大的升序子数列 所以一路回溯上去 每个被处理过的数列自然都能保持升序 这就是递归从局部到整体的智慧（其实在校内学习数列的递推公式的时候相信已经有很多同学都已经感受到了)
这里给出一个演示视频 可以直观的展示出归并排序的处理顺序以帮助我们理解
所以讲了那么多 归并和逆序数有什么关系？ 我们选择通过改造归并排序来求逆序数 就是因为归并排序本身就具有求逆序数的优势
对于逆序列这个概念 就是说对于一种排列情况 如果一个编号比另一个编号大 而这个更大的编号又排在小编号的前面 这种情况下我们称这两个编号形成一个逆序对 这种排列情况所有逆序对的数量就称为这种情况的逆序数 比如排列情况321 对3而言前面没有数字了 因此没有逆序对 而对2而言 它前面的3比2大 于是两者构成逆序对(3,2)
在上文所说的”擂台赛“中 两个指针所指向的数字发生比较时 只会有两种情况：第一种情况 左节点指针所指向的数小于右节点指针所指向的数字 我们填入左节点指针所指向的数字 或者第二种情况 右节点指针所指向的数字小于左节点指针所指向的数字 我们填入右节点所指向的数字 然而在上文中我就提到 归并排序递归树中每一个子序列都是对应原序列中的固定序数区间的 也就是说左节点的子序列在原序列中一定排在右节点子序列的前面 于是注意到第二种情况中 右节点指针所指向的数字小于左节点指针所指向的数字 同时右节点指针所指向的数字在原序列中又排在左节点指针所指向数字的右边 因此这两个数字将会形成一个逆序对 不仅如此 由于在归并排序的递归树中 每个节点所包含的子序列都是升序的 所以在第二种情况左节点所包含的数列中 所有位于左节点指针所指数字右边的数字全部比左节点指针所指数字要大 自然也就比右节点指针所指数字要大 所以它们各自都和右节点指针所指数字形成逆序对
设左节点所包含n个数字 此时左节点指针指向第i个数字 那么此时左节点包含子序列中位于左节点指针所指数字右边的共有n-i+1个 也就逆序数需要加上n-i+1 我们定义一个num表示逆序数 在归并排序中每遇到过一次上文所述的第二种情况 num就加上n-i+1 在归并排序结束后num的最终取值就是该排列情况的逆序数了
最后 是时候把字典序全排列和归并逆序数结合在一起 得到最终的程序了 我们只需要在全排列每次答案数组已满 需要输出答案数组的时候一并调用一次归并逆序数 然后再输出逆序数即可 下面是它们的代码
1.C++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#pragma GCC optimize(2)
#define N 1010
bool val[N]; //数字库
int output[N],a[N],temp[N];
//答案数组 子节点所包含的子序列数组 临时数组
int n,len;
int num;
void inverse_number(int l,int r){ //归并求逆序数
if(l==r)return;
int mid=(l+r)>>1;
inverse_number(l,mid); //分割成两部分 分别递归
inverse_number(mid+1,r);
memset(temp,0,sizeof(temp));
int pos,pos1,pos2;
pos=pos1=l;pos2=mid+1;
while(pos1<=mid&&pos2<=r){ //开始"擂台赛"比较
if(a[pos1]<=a[pos2]){ //第一种情况
temp[pos++]=a[pos1++];
}else{ //第二种情况
temp[pos++]=a[pos2++];
num+=(mid-pos1+1); //逆序数更新
}
}
for(int i=pos1;i<=mid;i++)temp[pos++]=a[i];
for(int i=pos2;i<=r;i++)temp[pos++]=a[i];
for(int i=l;i<=r;i++)a[i]=temp[i]; //将临时数组填入到节点数组作为更新
return;
}
void dfs(int x){ //深搜求字典序全排列
if(x==n){ //在答案数组已满时
num=0;
for(int i=1;i<=len;i++){
a[i]=output[i];
printf("%d",output[i]); //输出排列情况
}
inverse_number(1,len); //计算逆序数
printf(" ");
for(int i=1;i<=len;i++)printf("%d",a[i]); //test 顺便给排个序
printf(" %d\n",num); //输出逆序数
len--;//将已挑选的数字放回到数字库 答案数组腾出一个位置
return; //回溯
}
for(int i=1;i<=n;i++){
if(val[i]){
output[++len]=i;
val[i]=false; //挑选一个数字 数字库中对应数字设为false
dfs(x+1); //递归
val[i]=true;//将已挑选的数字放回到数字库 对应数字重新设为true
}
}
len--;//将已挑选的数字放回到数字库 答案数组腾出一个位置
return;//回溯
}
signed main(int *argc,char *argv[]){
memset(val,true,sizeof(val));
scanf("%d",&n);
len=0;
dfs(0);
return 0;
}2.Java
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static final int N = 1010;
static boolean []val=new boolean[N];
static int []output=new int[N];
static int []a=new int[N];
static int []temp=new int[N];
static int n,len;
static int num;
public static void inverse_number(int l,int r){ //归并求逆序数
if(l==r)return;
int mid=(l+r)>>1;
inverse_number(l,mid);
inverse_number(mid+1,r);
Arrays.fill(temp,0);
int pos,pos1,pos2;
pos=pos1=l;pos2=mid+1;
while(pos1<=mid&&pos2<=r){
if(a[pos1]<=a[pos2]){
temp[pos++]=a[pos1++];
}else{
temp[pos++]=a[pos2++];
num+=(mid-pos1+1);
}
}
for(int i=pos1;i<=mid;i++)temp[pos++]=a[i];
for(int i=pos2;i<=r;i++)temp[pos++]=a[i];
for(int i=l;i<=r;i++)a[i]=temp[i];
return;
}
public static void dfs(int x){
if(x==n){
num=0;
for(int i=1;i<=len;i++){
a[i]=output[i];
System.out.printf(output[i]+" ");
}
inverse_number(1,len);
System.out.printf(" ");
for(int i=1;i<=len;i++)System.out.printf(a[i]+" ");
System.out.printf(" "+num+"\n");
len--;
return;
}
for(int i=1;i<=n;i++){
if(val[i]){
output[++len]=i;
val[i]=false;
dfs(x+1);
val[i]=true;
}
}
len--;
return;
}
public static void main(String []args) {
Scanner input=new Scanner(System.in);
Arrays.fill(val, true);
n=input.nextInt();
len=0;
dfs(0);
return;
}
}
3.Python
N=1010
val=[True for i in range(0,N)]
output=[0 for i in range(0,N)]
a=[0 for i in range(0,N)]
temp=[0 for i in range(0,N)]
n=0;len=0
num=0
def inverse_number(l,r):
if l==r :
return
mid=(l+r)>>1
inverse_number(l,mid)
inverse_number(mid+1,r)
temp=[0 for i in range(0,N)]
pow=0;pos1=0;pos2=0
pos=pos1=l
pos2=mid+1
while pos1<=mid and pos2<=r :
if a[pos1]<=a[pos2]:
temp[pos]=a[pos1]
pos+=1;pos1+=1
else :
temp[pos]=a[pos2]
pos+=1;pos2+=1
global num
num+=(mid-pos1+1)
for i in range(pos1,mid+1):
temp[pos]=a[i]
pos+=1
for i in range(pos2,r+1):
temp[pos]=a[i]
pos+=1
for i in range(l,r+1):
a[i]=temp[i]
def dfs(x):
global len
if x==n :
global num
num=0
for i in range(1,len+1):
a[i]=output[i]
print(output[i],end="")
inverse_number(1,len)
print(end=" ")
for i in range(1,len+1):
print(a[i],end="")
print(" {}".format(num))
len-=1
return
for i in range(1,n+1):
if val[i]==True :
len+=1
output[len]=i
val[i]=False
dfs(x+1)
val[i]=True
len-=1
n=int(input())
len=0
dfs(0)
运行结果 这里以1~4的全排列为例：
C++：
Java:
Python :