告诉你什么是优雅的代码(8)-----排列组合专题

http://www.iteye.com/topic/770382提到：

4.1~20的整数的全排列，因为不才以前也研究过排列组合的问题，于是有了本专题。

最近的专题更多的是在给条鱼人家吃，没有讲怎么捕鱼。所以今天在介绍优雅代码之前，提出一个解决问题的方法论。

复杂问题都是由简单问题组成的，先解决简单问题。

言简意赅，任何复杂问题都是纸老虎。当你面对99*99时，你就要考虑将他变成1+1，然后解决1+1。

有了这个方法论，面对1-20的全排列。你知道怎么做了吧。没错，转变成AB的全排列。

AB:  AB  BA

太简单了，加个“C”吧。

ABC:  ABC ACB BAC BCA CAB CBA

看见标红色的字母了吧，无视它的存在, 就变成了 AB ，BC，AC 的 全排列。

大问题可沿用小问题的解法,让你想到了什么。一个是递归，一个是动态规划。这里显然适合用递归。
假设有n个字符，基本的算法就是：
1.n>2时，变成n-1问题
2.n=2时，输出
3.滚动数组

于是，一个优雅的方案浮出水面：

/**
 * 创建时间：2010-9-25 下午12:22:15
 * 项目名称：Test
 * @author Y.Guo
 * @version 1.0 
 * @since JDK 1.6
 * 文件名称：FullArrange.java
 * 类说明：全排列
 */
public class FullArrange {
	private char[] element;
	private int length;
	public void arrange(char[] element){
		this.element = element;
		this.length = element.length;
		deal(length);
	}
	private void deal(int size){
		if(size == 1)
			return;
		for (int i = 0; i < size; i++) {
			deal(size - 1);
			if(size == 2){
				print();
			}
			rotate(size);
		}
	}
	private void rotate(int size) {
		int firstP = length - size;
		char first = element[firstP];
		int i;
		for (i = firstP + 1; i < length; i++) {
			element[i - 1] = element[i];
		}
		element[i -1] = first;
		
	}
	private void print() {
		for (int i = 0; i < length; i++) {
			System.out.print(element[i]);
		}
		System.out.print("\t");
		
	}

	
	public static void main(String[] args) {
		FullArrange tool = new FullArrange();
		char[] elem = {'1','2','3','4','5'};
		tool.arrange(elem);
	
	}
	
}

至于组合问题，请听下回分解。

评论

5 楼 chinadeng 2010-10-29  

正需要这方面的内容 多谢多谢！！！！！！！！
忘牛人继续写博

4 楼 yangguo 2010-10-10  

tianshiyeben 写道

引用文字:

引用

文字

或者

javaeye 写道

文字

(alt+q)

what the hell are you talking about?

3 楼 tianshiyeben 2010-10-09  

引用文字:

引用

文字

或者

javaeye 写道

文字

(alt+q)

2 楼 yangguo 2010-09-25  

躁动的绵羊 写道

为什么要留言才给代码？为什么不把代码传上来呢？其实大家都想看看代码的解法，楼主就贴上代码吧

免得给那些隐藏癖，新手癖的也跑来看。好吧，我重贴一下。

1 楼 躁动的绵羊 2010-09-25  

为什么要留言才给代码？为什么不把代码传上来呢？其实大家都想看看代码的解法，楼主就贴上代码吧