排列和组合是组合学最基本的概念。
组合，则是指从给定的若干个元素中取出指定个数的元素，不考虑顺序。
排列，就是指从给定的若干个元素中取出指定个数的元素，并且要考虑顺序。
总之，排列与元素的顺序有关，组合与元素的顺序无关。例如：abc和bca是同一个组合，但却是两个排列。
组合
1.最容易想到的，一个集合里取n个元素进行组合。
代码如下：
import java.util.Arrays;
/**
* 模拟进制：一个集合里取n个元素进行组合
* @author Jeby
*
*/
public class CombineOfn {
public static void main(String[] args) {
String[] s = {"a", "b", "c", "d", "e"};
combine(s,3);
}
public static void combine(String[] s, int n) {
int[] dig = new int[s.length]; //进位用数组
StringBuilder state = new StringBuilder();
for (int i=s.length-1, j=0; i>=0; i--, j++) { //初始化进位数组状态
if (s.length-i>n) { //如s有5个元素，n为2，即取2个元素组合
dig[i] = 0; //那么初始状态为 00011
}
else {
dig[i] = 1;
}
state.append(dig[i]);
}
String max = state.toString(); //获取进位的最大状态，如上面的假设 11000
String min = state.reverse().toString(); //获取进位的最小状态，即数组初始状态 00011
while (max.compareTo(min) >= 0) { //当最小状态比不大于最大状态的时候循环
if (min.length()-min.replaceAll("1", "").length() == n) { //当进位状态中
for (int i=0; i<s.length; i++) { //1的个数为n时打印
if (dig[i] == 1) {System.out.printf("%s ", s[i]);}
}
System.out.println();
}
dig[dig.length-1]++; //模拟进位，末位+1
for (int i=dig.length-1; i>0; i--) {
if (dig[i] == 2) { //当某位进位位置达到最大状态时
dig[i] = 0; //清0
dig[i-1]++; //往前进位
} else {
break; //不满足进位 break
}
}
min = Arrays.toString(dig).replaceAll("\\D+", ""); //重新获得进位状态
}
}
}
2.迭代一个集合的全部组合。
例如，[a,b,c]的全部组合为[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]
代码如下：
import java.util.ArrayList;
import java.util.List;
/**
* 迭代全部组合
*
* 【效果】
* 原序列：
*[a, b, c]
*全部组合序列：
*[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]
* @author Jeby
*
*/
public class Combinations {
/**
* 取组合方法
* 参数： list原始数组
* 返回： 包含所有组合数组的数组
*/
public static List<List<Object>> getCombinations(List<Object> list) {
List<List<Object>> result = new ArrayList<List<Object>>();
List<Object> combine = null;
long n = (long)Math.pow(2,list.size());
for (long li=0L; li<n; li++) {
combine = new ArrayList<Object>();
for (int i=0; i<list.size(); i++) {
if ((li>>>i&1) == 1)
combine.add(list.get(i));
}
result.add(combine);
}
return result;
}
/**
* 测试
*/
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<Object>();
list.add("a");
list.add("b");
list.add("c");
List<List<Object>> result = getCombinations(list);
System.out.println("原序列：");
System.out.println(list.toString());
System.out.println("全部组合序列：");
System.out.println(result.toString());
}
}3.多个集合中分别取出一个元素进行组合。
代码如下：
/**
* 模拟进制：多个集合中分别取出一个元素进行组合
* @author Jeby
*
*/
public class CombinateByte {
public static void main(String[] args) {
String[][] s = {{"a","b"}, {"c", "d", "e"}, {"f", "g"}};
combie(s);
}
private static void combie(String[][] s) {
int[] dig = new int[s.length]; //用来模拟进位
while (dig[0] < s[0].length) { //进位最高位不满最大的时候循环
for (int i=0; i<s.length; i++) {
System.out.print(s[i][dig[i]]); //打印每个数组的当前进位位置的元素
}
System.out.println(); //换行
dig[dig.length-1]++; //模拟进位，末位+1
for (int i=dig.length-1; i>0; i--) {
if (dig[i] == s[i].length) { //当某进位位置达到最大时往前进位
dig[i] = 0; //当前位清0恢复最小状态
dig[i-1]++; //进位
} else {
break; //不满足进位时break
}
}
}
}
}
排列
1.获得集合全排列的一个实现算法。
代码如下：
import java.util.Arrays;
/**
* 获得数组全排列的一个实现算法
*
*/
public class TestAllP {
static String[] array = { "x", "y", "z" };
public static void main(String[] args) {
getAllOrder(array,0,array.length - 1);
}
public static void getAllOrder(Object[] arr,int begin, int end) {
if (begin == end) {
check();
} else {
for (int i = begin; i <= end; i++) {
swap(arr,begin, i);
getAllOrder(arr,begin + 1, end);
swap(arr,i, begin);
}
}
}
/**
* 这里应该加上各种防止无效交换的情况,比如位置相同，或者2个位置的数据相同
*/
public static void swap(Object[] arr,int from, int to) {
if (from == to) {
return;
}
Object tmp = arr[from];
arr[from] = arr[to];
arr[to] = tmp;
}
/**
* 排列拿到了，可以进行进一步的筛选了。
*/
public static void check() {
System.out.println(Arrays.toString(array));
}
}2.获得一个集合中若干个元素的排列，可以结合从一个集合里取n个元素进行组合然后再对每一组组合数据进行全排列，在此不再累述。