排列组合算法

时间：2022-05-30 11:08:08

排列和组合是组合学最基本的概念。

组合，则是指从给定的若干个元素中取出指定个数的元素，不考虑顺序。

排列，就是指从给定的若干个元素中取出指定个数的元素，并且要考虑顺序。

总之，排列与元素的顺序有关，组合与元素的顺序无关。例如：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个元素进行组合然后再对每一组组合数据进行全排列，在此不再累述。

 

 

标签：
相关文章