排列组合算法(JAVA实现)

组合算法实现 

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

实现方法一： 

// 组合算法 
// 本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标 
// 代表的数被选中，为0则没选中。 
// 首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。 
// 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为 
// “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。 
// 当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得 
// 到了最后一个组合。 
// 例如求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' }; 
}