排列组合-插入算法

排列组合-插入算法

1.问题描述
    将字符'1','2','2','3','4'的所有的组合用一个算法排列出来。
2.问题分析
    这是一个排列问题，排列个数与参与排列的元素个数有关。假设参与排列的元素个数
为n，那么排列数等于n的阶乘，即F（n）=n!。n! = 1 * 2 * 3 * ... * n.
本文问题描述中出现了重复元素，最后排列中有很多重复的排列需要去掉。本文介绍一种插入算法来解决这个问题。
所有的插入算法的一个共同点：从最小问题单元开始递推。
结合下面的图示开始递推。

图2-1

    (1)当只有一个元素时，排列数为1，即一种排列。排列：[1]
    (2)当有两个元素时，排列数为2。排列：[2,1],[1,2]
    (3)当有三个元素时，排列数为1 * 2 * 3 = 6。排列：[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]
    ......
    以此类推。
3.算法实现
将一个字符查到一个排列字符数组中：

char [][] insert(char [] a,char b) {
	int row = a.length+1;
	int col = row ;
	int insertPos = 0;//插入位置
	char [][] r = new char[row][col];
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if(j < insertPos) {
				r[i][j] = a[j];
			} else if(j > insertPos ){
				r[i][j] = a[j-1];
			} else {
				r[i][j] = b;//插入新的字符
			}
		}
		insertPos++;//插入位置向后移动
	}
	return r;
}

主算法：

char [][] composition(char [] c) {
	//存储排列组合后的结果
	char [][] r = {{c[0]}};
	//存储每次插入一个字符以后的所有结果。
	char [][][] d ;
	int ii;
	for (int i = 1; i < c.length; i++) {
		d = new char[r.length][0][0];
		//插入新的字符
		for (int j = 0; j < r.length; j++) {
			d[j]=insert(r[j],c[i]);
		}
		//将d中的结果存放到r
		r = new char[d.length*d[0].length][0];
		ii = 0;
		for (int j = 0; j < d.length; j++) {
			for (int j2 = 0; j2 < d[j].length; j2++) {
				r[ii++] = d[j][j2];
			}
		}
	}
	return r;
}

过滤算法：

Set<String> removeRepeat(char [][]r) {
	Set<String> set = new HashSet<String>();
	for (int i = 0; i < r.length; i++) {
		set.add(new String(r[i]));
	}
	return set;
}

4.扩展
    当有重复元素时，最后排列数为多少？
     在回答上面的问题之前我们先通过本文中的算法测试一下。
     测试代码：

public static void main(String[] args) {
	Composition com = new Composition();
//	new char[]{'1','2','3','4','2','2'}
//	new char[]{'1','2','3','4','2','2','2'}
	char [][] r = com.composition(new char[]{'1','2','3','4','2'});
	System.out.println(r.length);//过滤前
	Set<String> set = com.removeRepeat(r);
	System.out.println(set.size());//过滤后
//	Iterator<String> it = set.iterator();
//	while (it.hasNext()) {
//		System.out.println(it.next());		
//	}
}

测试结果：
    (1)重复一次时，（这里重复元素为2）：

new char[]{'1','2','3','4','2'}
结果：120,60

    (2)重复两次时：

new char[]{'1','2','3','4','2','2'}
结果：720,120

    (3)重复三次时：

new char[]{'1','2','3','4','2','2','2'}
结果：5040,210
    ......

    通过逐一排列的过程可知，在排列中所有对于一个元素的所有重复元素在排列中的任何位置的机会概率是均等的。假设只有一个元素重复，则一个元素重复m次（总共有m+1个元素）后最终的排列数为F(n)= n!/(m+1)!。
5.总结
    通过本文的学习，大家至少知道了一种排列的算法【插入算法】。但这不是最重要的，重要的是学会如何去分析，分解问题。将复杂问题简单化，找到其最小问题单元。从最简单的入手。因为人本身的Memory，CUP和Hard与计算机相比极为有限，并且这种差距还在与日俱增。所以我们只能先处理好最简单的最基本的问题，在接触计算机帮助我们处理复杂问题。