利用递计算全部数组组合的算法求教

利用递计算所有数组组合的算法求教
这个算法的意思大概如下，将1，2，3，4，5...n的数字进行组合,他使用了一种表现分组的形式,以防止分组的重复,在分组内数字减小，在不同分组之间的第一个数字呈现增大。如{1，3，2，4，5}则实际分组为1,23,4,5，而{1,4,2,3,5}这种形式是不符合规定的（在不同分组之间的第一个数字呈现增大），若要表示该分组应表示为{1，3，4，2，5}
代码如下

import java.util.Arrays;


public class a{

	public static void main(String[] args){

		genSetPart(new int[]{3,67,3,6,4},5);

	}

static void genSetPart(int a[], int i) {

if ( i > 0 ) {

int j, head = i;

for ( j = i; j < a.length; ++j ) {

if ( head < a[j] ) {

a[j-1] = i;

genSetPart(a, i-1);

head = a[j];

}

a[j-1] = a[j];

}

a[j-1] = i;

genSetPart(a, i-1);

for ( j = a.length-1; j >= i; --j ) a[j] = a[j-1];

} else

System.out.println(Arrays.toString(a));

}}

无论我输入的数组是什么，输出的组合永远都是1,2,3...i的组合，这段代码完全看不懂，求解释，希望给点注释和点播

算法

------解决方案--------------------
它这个代码只能做1~i的组合，跟数组内容完全没关系。。。

我觉得这个题用全排列然后过滤就挺好理解的了



public class Main {

	public static void main(String[] args) {

		perm(new int[] { 1, 2, 3, 4 }, 0, 3);

	}


	/**

	 * buf 处理数组

	 * start 起始位置

	 * end 终止位置 

	 */

	public static void perm(int[] buf, int start, int end) {


		if (start == end) {

			int head = buf[0];

			for (int i = 1; i <= end; i++) {

				if (buf[i] > buf[i - 1]) {

					if (buf[i] < head)// 不符合要求的，当前元素大于上一分组最后一个元素且小于上一分组第一个元素

						return;

					head = buf[i];

				}

			}


			for (int i = 0; i <= end; i++) {
System.err.print(buf[i]);

			}

			System.err.println();


		} else {


			for (int i = start; i <= end; i++) {


				int temp = buf[start];

				buf[start] = buf[i];

				buf[i] = temp;


				perm(buf, start + 1, end);


				temp = buf[start];

				buf[start] = buf[i];

				buf[i] = temp;


			}

		}

	}

}

------解决方案--------------------
用了将近1天时间把代码分析出来了，强烈要求楼主给分



import java.util.Arrays;


public class Test_Part {

	/*

	 * 该方法用于打印出所有满足以下条件的排列： 1）排列包含1、2、3……n，共n个元素。

	 * 2）排列内可以分组，分组内部的数字按降序排列，分组之间按升序排列。

	 * 例如有5个元素的排列2、3、4、1、5是符合条件的排列，可以任务这5个元素是这样分组的

	 * ——（2）、（3）、（4、1）、（5），其中分组之间2<3<4<5,分组内部4>1。

	 * 该方法的原理是依次将n、n-1……3、2、1加入排列，寻找满足条件的所有排列情况。

	 * 还是以5个元素的排列为例，先将5加入排列，只有一种满足条件的排列那就是（5）；

	 * 然后将4加入排列，可以得到两种满足条件的排列{（4）、（5）}和{（5、4）}；

	 * 继续将3加入排列，对于排列{（4）、（5）}加入3后可以得到3中合法的排列

	 * {（3）、（4）、（5）}、{（4、3）、（5）}和{（4）、（5、3）}，

	 * 对于排列{（5、4）}加入3后可以得到两种合法的排列{（3）、（5、4）}和{（5、4、3）}，

	 * 所以加入3后一共得到5种合法的排列方式{（3）、（4）、（5）}、{（4、3）、（5）}、{（4）、（5、3）}、{（3）、（5、4）}和{（5、4、3）}；

	 * 继续依次递归加入2和1、就可以得到共52中合法的排列，然后递归调用i=0，用于打印合法排列

利用递计算全部数组组合的算法求教

相关推荐