完备置换阵列的两种代数枚举方法

摘要 完备置换阵列(CPA)是定义在集合Zn=｛1,2,…,n｝上的所有n!个排列,n个正整数的每一种排列称为一个置换.随着n的增加,n!个置换的完全排列是很困难的工作.本文提出两种n!个置换的枚举方法,不同于传统的比较回溯法和字典排序法,而是借助于完好定义的操作函数来执行从一个置换到另一个置换的状态转移,所形成的完备置换阵列具有天然的组合结构特征.第一种方法是将完备置换阵列按照格雷码的结构特征进行排序,通过有限状态机执行操作函数来达到枚举基于格雷码排序的n!个置换的目的.第二种方法是基于组合数学的方法,借助于循环移位拉丁方来形成n!个置换的排列