改进全排列算法构造任意阶幻方

摘要：幻方的构造方法很多，但是多数方法只能构造出少数几个幻方，而不能构造出全部幻方。本文的改进全排列算法能构造出所有幻方。本文给出改进全排列算法的原理和步骤，并设计程序验证算法，程序的运行结果和运行时间表明算法是正确可行的。最后给出本算法求得的所有3阶幻方和部分4阶幻方。

关键词：幻方 全排列 任意阶 构造 算法

中图分类号：O144 文献标识码：A 文章编号：1007-9416（2013）08-0116-02

1 前言

阶幻方是由之间不重复的自然数组成的阶方阵，且方阵的每行、每列、主对角线和副对角线上的元素和均相等，这个和被称为幻和。幻方在哲学、美学、美术设计、计算机程序设计、图论、人工智能、对策论、组合分析等方面有广泛的应用。此外，趣味数学、棋类游戏也都与幻方有着内在的联系，如围棋和象棋的走法原理均同幻方的布局原理有关。

幻方的构造方法有很多，如文献[1]的镶边法、文献[2]的菱形法和比例放大法，等等。但是目前的幻方构造方法只能构造出极少几个幻方，而不能构造出全部幻方。本文将使用之间元素的全排列构造所有阶幻方。

2 全排列构造幻方

2.1 全排列的定义

从个不同元素中任取个元素，按照某特定的顺序排列起来，则将这个元素叫做一个排列。当时叫个元素的全排列。个元素的全排列有个。如：3个元素{a，b，c}的全排列有abc，acb，bac，bca，cab，cba，共6个。

2.2 全排列的构造

全排列的构造方法有很多，本文使用字典序法[7]。

个元素的所有全排列的构造思路是，从第1个排列开始，依次找当前排列的下一个排列，直到最后一个排列。得到一个排列的下一个排列的方法如下：

步骤1：从当前排列的最右端一个元素开始，找到第1个满足条件“它左边的元素比它小”的元素，并记下此元素的左边元素的序号为。

步骤2：从当前排列的最右端一个元素开始，找到第1个比第个元素大的元素，并将此元素和第个元素交换位置。

步骤3：将当前排列的第个元素到最右端元素之间的元素倒序排。

这样就得到了当前排列的下一个排列。

例如：754938621是数字1-9的一个排列，使用上述方法求其下一个排列是754961238。

2.3 全排列构造幻方的算法思想

预求阶幻方，先求得数字的所有全排列，再将每个全排列的元素按照先左后右、先上后下的顺序依次放入阶方阵中，然后判断此方阵是否为幻方。此方法的时间复杂度很高，是级的。仅4阶幻方的构造程序就运行30多个小时。

为此需对算法进行改进。其实，个全排列中有很多全排列使用上述方法是不能转换为幻方的。假设是的一个全排列，如果不等于阶幻方的幻和，那么所有以开头的全排列均不能构造出幻方，所以我们需跳过以开头的所有全排列。这样一次就节约出了构造个全排列的时间。即便等于阶幻方的幻和，但若不等于阶幻方的幻和，那么所有以开头的全排列也需跳过。以此类推，我们一边判断幻方成立的条件，一边构造全排列，最终将算法的复杂度降为级。

3 改进全排列算法构造幻方

3.1 算法描述

欲求阶幻方，具体方法如下：

步骤1：初始化排列，排列 ，变量为1，计算阶幻方的幻和并记为，将赋给。

步骤2：计算的第个到第个元素的和并记为，若不等于转步骤3，否则转步骤4。

步骤3：将排列的第个到最后一个元素按从大到小的顺序重新排列，然后使用2.2中的字典序法得到排列的下一个排列，将赋给，转步骤2。

步骤4：。

步骤5：如果，就将置1并转步骤6；否则转步骤2。

步骤6：将中元素从上到下、从左到右依次放入一个阶方阵中，判断此方阵是否为幻方。

步骤7：使用2.2中的字典序法得到排列的下一个排列，将赋给。

步骤8：判断是否与排列相同，若相同转步骤9，否则转步骤2。

步骤9：算法结束。

3.2 构造结果

使用java语言编写3.1算法的程序，得到了所有的3阶和4阶幻方，其中3阶幻方有8个，4阶幻方有7040个。构造4阶幻方时程序运行时间为466066毫秒，而改进之前程序运行时间是30多个小时，这说明算法的复杂度大大降低了。程序运行结果表明3.1算法是正确可行的，且能构造出所有的阶幻方。

下面是3.1算法的核心java代码。

int p[]=new int[n*n]，end[]=new int[n*n]；

int huanhe=n*（n*n+1）/2；//n阶幻方的幻和

int sum=0；//计算求得的幻方个数

int s，k=1；

for（int i=0；i

for（int i=0；i

do{

if （huanhe！=add（p，k-1，k+n-1）） { //add方法计算排列p的第k个到第k+n个元素的和

p=next_tiao（p，k-1+n）；//方法next_tiao将排列p的第k+n个到最后一个元素从大到小排序

p=next（p）；//方法next是使用2.2算法计算当前排列的下一个排列

continue； }

else {

k=k+n；

if （k>n*n-n）{

k=1；

if （isHuan（p，n）） sum++； //isHuan方法是判断排列p是否能构成n阶幻方

p=next（p）；

}

}

}while（equals（p，end））；//equals方法是判断排列p是否与end相同

图1是3.1算法所构造出的所有3阶幻方，图2是3.1算法所构造的前64个4阶幻方。图中，幻方之间用“*”分隔。

4 结语

多数幻方构造方法只能得到部分幻方，很难得到所有的幻方，而此算法能得到所有的阶幻方。本文的改进全排列算法能构造出所有的幻方，不足之处是算法复杂度有些高，所以当幻方阶数稍大时算法的运行时间会很长。今后还需对此算法再进一步改进，以便能适合大阶幻方的构造。

参考文献

[1]林淑飞.改进镶边法构造任意阶幻方[J].安徽大学学报（自然科学版），2008，32（4）：14-17.

[2]林淑飞，朱艳伟.构造任意阶幻方的一种方法[J].云南民族大学学报（自然科学版），2008，17（1）：40-43.

[3]呂振洪.幻方问题的搜索方法研究[J].仪器仪表学报，2009，30（6）：375-378.

[4]ZHANG Zhen-yue， Wang Jing， ZhA Hong-yuan.Adaptive manifold learning[J].IEE- E Trans Pattern Analysin and Machine Intllligence，2012，34（2）：253-265.

[5]顾艳春.一种改进的局部切空间排列算法[J].计算机应用研究，2013，30（3）：728-732.

[6]吴鹤龄.幻方及其他——娱乐数学经点名题（第二版）[M].北京：科学出版社，2004：1～356.

[7]殷剑宏.组合数学[M].北京：机械工业出版社，2006：10-88.

推荐访问:构造 算法 排列 改进 任意