Java开发

J2SE 竞赛中常见的排列组合算法

页面
字体
小树 · 3月24日 · 2014年 · · ·

本篇主要讲述以下组合和排列的算法,作为众多高级算法的基层算法,对它的优化和理解是十分重要的,这也是在很多的J2SE算法的竞赛中必出的一种题目。

组合算法实现
从m个数里面取n个数的算法。最容易理解的就是递归,但是其效率太低。

组合算法

本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标

代表的数被选中,为0则没选中。

  1. 首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。
  2. 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为
  3.  “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
  4.  当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得
  5.  到了最后一个组合。
  6.  例如求5中选3的组合

// 1 1 1 0 0 //1,2,3
// 1 1 0 1 0 //1,2,4
// 1 0 1 1 0 //1,3,4
// 0 1 1 1 0 //2,3,4
// 1 1 0 0 1 //1,2,5
// 1 0 1 0 1 //1,3,5
// 0 1 1 0 1 //2,3,5
// 1 0 0 1 1 //1,4,5
// 0 1 0 1 1 //2,4,5
// 0 0 1 1 1 //3,4,5

import java.util.ArrayList;   
import java.util.List;   

/**  
* 面试中遇到的问题,在网上查找资料,加上自己的总结, java 代码实现组合的算法  
* 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1 该方法比较好理解,但具体算法的分析却有难度。  
*  
* @date 
* @author 
*  
*/   
class Zuhe1 {   

/**  
* @param a:组合数组  
* @param k:生成组合个数  
* @return :所有可能的组合数组列表  
*/   
private List zuhe(int[] a, int m) {   
   Zuhe1 zuhe = new Zuhe1();   
   List list = new ArrayList();   
   int n = a.length;   

   boolean flag = false; // 是否是最后一种组合的标记   

   // 生成辅助数组。首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。   
   int[] tempNum = new int[n];   
   for (int i = 0; i < n; i++) {   
    if (i < m) {   
     tempNum[i] = 1;   

    } else {   
     tempNum[i] = 0;   
    }   
    System.out.print(tempNum[i]);   
   }   
   print(tempNum);// 打印辅助数组   

   list.add(zuhe.createResult(a, tempNum, m));// 打印第一中默认组合   

   do {   
    int pose = 0; // 记录改变的位置   
    int sum = 0; // 记录改变位置 左侧 1 的个数   
    // 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”   
    for (int i = 0; i < (n - 1); i++) {   
     if (tempNum[i] == 1 && tempNum[i + 1] == 0) {   
      tempNum[i] = 0;   
      tempNum[i + 1] = 1;   
      pose = i;   
      break;   
     }   
    }   
    print(tempNum);// 打印辅助数组   
    list.add(zuhe.createResult(a, tempNum, m));// 打印第一中默认组合   

    // 同时将其左边的所有“1”全部移动到数组的最左端。   

    for (int i = 0; i < pose; i++) {   
     if (tempNum[i] == 1)   
      sum++;   
    }   

    for (int i = 0; i < pose; i++) {   
     if (i < sum)   
      tempNum[i] = 1;   
     else   
      tempNum[i] = 0;   
    }   

    // 判断是否为最后一个组合:当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。   
    flag = false;   
    for (int i = n - m; i < n; i++) {   

     if (tempNum[i] == 0)   
      flag = true;   

    }   
   } while (flag);   

   return list;   
}   

// 根据辅助数组和原始数组生成 结果数组   
public int[] createResult(int[] a, int[] temp, int m) {   
   int[] result = new int[m];   

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

    if (temp[i] == 1) {   
     result[j] = a[i];   
     System.out.println("result[" + j + "]:" + result[j]);   
     j++;   

    }   
   }   

   return result;   
}   

// 打印   
public void print1(List list) {   

   for (int i = 0; i < list.size(); i++) {   
    System.out.println();   
    int[] temp = (int[]) list.get(i);   
    for (int j = 0; j < temp.length; j++) {   
     System.out.print(temp[j] + " ");   
    }   
   }   
}   

// 打印整数数组的方法   
public void print(int[] a) {   
   System.out.println("生成的辅助数组为:");   
   for (int i = 0; i < a.length; i++) {   
    System.out.print(a[i]);   
   }   
   System.out.println();   
}   

public static void main(String[] args) {   
   int[] a = { 1, 2, 3, 4, 5 }; // 整数数组   
   int m = 3; // 待取出组合的个数   
   Zuhe1 zuhe = new Zuhe1();   
   List list = zuhe.zuhe(a, m);   
   zuhe.print1(list);   

}   
}

实现方法二:使用递归算法,但比较难于理解,摘自网上,慢慢消化

 

    /**  
    * 从n个数里取出m个数的组合是n*(n-1)*...*(n-m+1)/m*(m-1)*...2*1  
    */   
    import java.io.*;   

    public class Test1 {   

    public static void main(String[] args) {   
       select(2);   
    }   

    private static void select(int k) {   
       char[] result = new char[k];   
       subselect(0, 1, result, k);   

    }   

    private static void subselect(int head, int index, char[] r, int k) {   
       for (int i = head; i < a.length + index - k; i++) {   
        if (index < k) {   
         r[index - 1] = a[i];   
         System.out.println("i="+(i)+";index="+(index));   
         subselect(i + 1, index + 1, r, k);   
        } else if (index == k) {   
         r[index - 1] = a[i];   
         System.out.println(";i="+(i)+";index="+(index)+";index==k:"+(index==k));   
         System.out.print(i+"===");   
         System.out.println(r);   
         subselect(i + 1, index + 1, r, k);   
        } else {   
         System.out.println("++");   
         return;//返回到何处?奇怪   
        }   

       }   
    }   

    private static char[] a = { 'a', 'b', 'c' };   
    }

其实还有更多的利用java已经封装了的类来实现这些算法的方法,但是归根究地还是离不开这么一种思想 , 所以多余的就不贴上来了。够用了。

转载必须注明来源: 小树技术博客 » J2SE 竞赛中常见的排列组合算法

101 条回应