配对序列生成算法实现与分析

配对算法实现与分析

这个也是做连连看时所写的算法，为了保持通用原则，这里一律采用数组实现

基本思路：

1.       先将所有元素填充到数组里，并把出现次数放到eCount[]里、最后出现的地址放到

lastAddr[]中。

2.       查看eCount[]此时数组里的各种元素出现的次数有双有单。

3.       找出两个eCount[x1],eCount[x2]为单的元素的lastAddr[x1]、lastAddr[x2]，并设置 data[lastAddr[x1]]=data[lastAddr[x2]]。

4.       这就完成了双去单。

/**

     * 产生范围在[start,end]区间的配对的序列， 填充到int[arrayRows>0][arrayCloums>0]的数组中，

     * 最后返回这个数组

     * 完美版，适用于任何情况

     *

     * @param start

     *            起始整数

     * @param end

     *            终点整数

     * @param arrayRows

     *            数组行数

     * @param arrayColums

     *            数组列数

     * @return 如果参数中数组行列值小于等于零或者数组大小为奇数，则返回null，否则

     *         返回已经填充了配对数的数组int[arrayRows][arrayCloums]

     */

    public static int[][] partnerUP(int start, int end, int arrayRows,

           int arrayColums) {

 

       if (arrayColums <= 0 || arrayRows <= 0

              || (arrayColums * arrayRows) % 2 != 0) {

           return null;

       }

       int[] eCount;// 元素计数器

       int[] lastAddr;// 元素最后出现的地址

       int[][] data = new int[arrayRows][arrayColums];// 保存配对序列数组

       int arraySize = arrayRows * arrayColums;// 数组大小

       int maxPartners = arraySize / 2;// 数组中可能出现的最大对数

      

       // 将start恒置为小的数，end为大的数

       if (end - start < 0) {

           int tmp = end;

           end = start;

           start = tmp;

       }

       // 填充范围,大于0

       int fillArea = Math.abs(end - start) + 1;

       // 填充范围是否大于最大配对数，如果是的，则只需maxPartens个填充因子就可以了

       boolean isOverPartner=(fillArea - maxPartners)>0? true:false;

       int[]fillElemts=new int[0];

       if (isOverPartner) {

           //定义maxPartners个格子用来装随机从fillArea中取出的填充因子

           fillElemts=new int[maxPartners];

           for(int i=0;i<fillElemts.length;i++){

              fillElemts[i]=start+(int)(Math.random()*fillArea);

           }

           //数组地址范围,计数器、最后地址数组地址范围

           fillArea=maxPartners;

           eCount = new int[fillArea];

           lastAddr = new int[fillArea];

       }else{

           eCount = new int[fillArea];

           lastAddr = new int[fillArea];

       }

       // 填充data[][]

       for (int i = 0; i < arraySize; i++) {

           // 随机产生一张图片索引

           int index = start + (int) (Math.random() * fillArea);

           // 对应索引计数+1

           eCount[index - start] += 1;

           if(isOverPartner){

              //选取抽取出来的元素

              data[i / arrayColums][i % arrayColums]=fillElemts[index-start];

           }else{

              // 将图片名称放入Data中

               data[i / arrayColums][i % arrayColums] = index;

           }

           // 将最后出现的地址赋给addrCount[index]保存

           lastAddr[index - start] = i;

 

       }

       // 图素配对开始（去单操作）

       // 从计数数组的最有一个元素开始

       int i = eCount.length - 1;

       // 出现的元素中数量为奇数的元素个数

       int pCount = 0;

       while (i > -1) {

           if (eCount[i--] % 2 == 1) {

              pCount += 1;

           }

       }

       // 如果确实存在奇数个元素

       while (pCount > 0) {

           for (int j = 0; j < eCount.length - 1; j++) {

              for (int k = 1; k < eCount.length; k++) {

                  if (eCount[j] % 2 == 1) {

                     if (eCount[k] % 2 == 1) {

                         // 计数器为奇数的图素地址交换(根据最后图素保存的地址进行交换操作)

                         data[lastAddr[j] / arrayColums][lastAddr[j]

                                % arrayColums] = data[lastAddr[k]

                                / arrayColums][lastAddr[k] % arrayColums];

                         eCount[j] -= 1;

                         eCount[k] += 1;

                         pCount -= 2;//去掉两个奇数素

 

                     }

                  }

              }

           }

       }// 图素配对结束

       return data;

    }

测试结果：

Xx代表方括号里的的数字

LLKTookit.partnerUP(x,x,4,4)

===========[1,15]

8,14,15,14,

10,8,2,1,

15,2,1,10,

14,8,14,8,

==============[-1，15]

-1,12,6,12,

3,6,6,6,

13,-1,6,15,

15,13,6,3,

==============[-1,-15]

-6,-5,-6,-6,

-9,-6,-6,-1,

-7,-9,-5,-7,

-15,-1,-6,-15,

=============[0,0]

0,0,0,0,

0,0,0,0,

0,0,0,0,

0,0,0,0,

=============[1,1]

1,1,1,1,

1,1,1,1,

1,1,1,1,

1,1,1,1,

==============[-1,-1]

-1,-1,-1,-1,

-1,-1,-1,-1,

-1,-1,-1,-1,

-1,-1,-1,-1,

分析：从代码上看，写得比较繁杂，从运行结果来看，该函数实现的还不错。

总结：这个方法的实现经历最初的内嵌版本，再是分离出来后的不完美版(有兴趣的可以看看，在下面)，知道今天改的自认为完美版，一路走来都意味着一次次的进步，和对完美的追求，今天写的这个配对算法和之前写的连线算法一起，作为我暑假连连看游戏制作的最终收获，我觉得，虽然不丰厚，但至少很值得。

 

不完美版代码，在注释中有 “为什么不完美的解释”

以下是word文档