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

本篇主要讲述以下组合和排列的算法，作为众多高级算法的基层算法，对它的优化和理解是十分重要的，这也是在很多的J2SE算法的竞赛中必出的一种题目。
组合算法实现
从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)…21 该方法比较好理解，但具体算法的分析却有难度。
@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 &lt; a.length + index - k; i++) {   
    if (index &lt; 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' };   
}</pre>

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