排列与组合

试想这样一个问题
一组数比如{1，3，4，7} 任取其中的三边，会构成多少种不同的三角型
又或者{2，2，4，5，10，12}任取其中四边，会构成多少种不同的多边形？如果取三边，或五边又如何？

在一些情况下，我们需要解决处理排列和组合数的问题
先来看一下排列的情况
          abcd
下标  1234

联系我们的问题再观察这个数组，其实我们需要做的就是在比方说1的位置，让a,b,c,d轮流出现1次，然后在2的位置，让abcd再次轮流出现，以此类推，直到最后2位处理完成之后。返回上级程序

解决一个数组平移的问题并不难
abcd 向左移动4次，就可以满足在1的位置上都出现一次。
那么紧接着下一步，如何让2的位置再次轮流出现abcd也仍然是使用相同的方法
每次移动一位后，查看右边的n个数，然后把问题抛给子问题
递归，分治法，是计算机解决问题的一个主要的手段
我们从问题中发现相似的处理方法，然后递归调用自身

int[] a = { 1, 2, 3, 4 };
// level start at 0
public void rotate(int level) {
         //it's last number
	if (level == a.length - 1)  return;
	int in = level + 1;
	for (int i = level; i < a.length; i++) {
		if (i == 0)
                  //print the number
		    log(a);
		Int t = a[level];
           //move the list
	         for (int j = level; j < a.length - 1; j++) 
			a[j] = a[j + 1];
		a[a.length - 1] = t;

		if (i != a.length - 1)
			log(a);
                  //Go into the subquestion
		rotate(in);
		}
	}

实际上我们做的就是旋转整个数组，当开始旋转N个数中的第一个数时，首先询问右边N-1个数是否已经旋转完成？如果没有则进入旋转右边的N-1个数的方法中，同理进入这个方法后再次询问右边N-2个数是否旋转完成？一直到最后1个数或是最后2个数已经旋转完成时，跳回到上级方法中继续执行。


组合：解决了排列的问题后，再来看组合就容易了许多,我们取C（4，2）的组合。红色代表取到的数
【1】
abcd
【2】
abcd
【3】
abcd
【4】
abcd
【5】
abcd
【6】
abcd

同排列，我们也在不断的遍历整个数组，每次询问是否子问题已经解决，即N+1位后的数是否已经全部遍历了？然后决定是否进入子问题。这里由于组合数取的范围，我们需要不断向右移动。在【4】【6】中，移动了红色编号的起始位置

解决了组合问题后，之前的多边型的题目就很简单了，在这里我们没有列举诸如2边相同的情况如{2，2，2，2，2}取其中3变可以构成多少个三角型，实际只有2，2，2 一种。因为所有的边都是相同的，因此还需要一些判断。另外一个多边型的任何一边必须小于其它所有边相加。

组合与排列代码：

public class Polygons{

	int[] a = { 1, 2, 3, 4 };
	int[] b = new int[4];
	
	//x为起始位置，设为0表从数组的第一个位置开始循环
	public void rotate1(int x) {
		if (x == a.length - 1) return;
		int in = x + 1;
		for (int i = x; i < a.length; i++) {
			if (i == 0)
				log(a);
			int t = a[x];
			for (int j = x; j < a.length - 1; j++) 
				a[j] = a[j + 1];
			a[a.length - 1] = t;
			if (i != a.length - 1)
				log(a);
			rotate1(in);
		}
	}
	/*
	 * x为0,意为从数组0的位置开始
	 * level为-1,描述循环层数
	 * y为取数组中的几个数作为组合，如取1则表示数组中的任意2个数的组合
	 */
	public void rotate2(int x, int y, int level) {
		if (level == y)
			return;
		level++;
		int in = x+1;
		for (int i = x; i < a.length; i++, in++) {
			b[level] = a[i];
			rotate2(in, y, level);
			if (level == y)
				log(b);
		}
	}

	public void log(int[] b) {
		for (int i : b) {
			System.out.print(i + " ");
		}
		System.out.println("");
	}

	public static void main(String[] args) {
		System.out.println("=====排列=====");
		new Polygons().rotate1(0);
		System.out.println("=====组合=====");
		new Polygons().rotate2(0, 2, -1);
	}
}