全排列生成算法:解析与证明
问题说明:算法:字典序算法: 参考:问题说明:
一个数组的全排列生成算法,是指将该数组所能形成的所有的“数字”,按照由小到大的顺序依次输出的算法。算法:
规律:
按序输出:按序输出说明只需要依次求出当前排列的后续排列,也就是比现在排列所生成的"数字"更大的那一个排列,就可以做到输出全部排列。逆序对/逆序数:一个数组是否按照递减顺序排列完好,与其逆序对的个数相关。对于一个已经排列完好的数组,其逆序对个数为0。
字典序算法:
算法说明:
以当前arr[]=1234555443210为例子:
1.找到当前排列arr的最大的可以不变的前缀arr[0,…,k-1],也就是找到 k m a x = m a x { k ∈ [ 1 , n ) ∣ a r r [ k + 1 ] > a r r [ k ] } k_{max}=max\{k\in[1,n) |arr[k+1]>arr[k] \} kmax=max{k∈[1,n)∣arr[k+1]>a
如果觉得《全排列生成算法:解析与证明》对你有帮助,请点赞、收藏,并留下你的观点哦!