利用递计算所有数组组合的算法求教
这个算法的意思大概如下，将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));
}}
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;
}
}
}
}
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，用于打印合法排列
* 另外每次加入i会覆盖掉第i-1个元素，所以不论数组里面原来是什么元素，在递归过程中会依次覆盖为n、n-1……i、i-1……3、2、1。
*/
public static void genSetPart(int a[], int i) {
// 当i>0的时候继续递归将i加入排列，当i=0的时候打印输出获得的合法的排列。
if (i > 0) {
// head为每个分组的第一个元素，初始时将i加入排列的第一个元素，作为单独的分组
int j, head = i;
// 从位置i到数组末尾，依次尝试放入i后是否是合法排列，如果时，使用当前合法排列，递归加入i-1
for (j = i; j < a.length; ++j) {
// 判断将当前分组的head与位置为j的元素比较，判断是否已到了分组的末尾，如果是，则将i放入j-1的位置将会得到合法的排列
if (head < a[j]) {
// 在循环过程中，可能设置从第i-1个元素到倒数第二个元素
a[j - 1] = i;
// 找到一种满足要求的排列，递归调将i-1加入排列
genSetPart(a, i - 1);
// 进入下一个分组，将head设置为下一个分组的第一个元素
head = a[j];
}
// 将位置为j的元素向左移动一个位置
a[j - 1] = a[j];
}
// 将i放入最后一个位置，获取最后一个满足条件的排列，除了使用下一分组的head判断当前分组结束之外，到达排列的末尾也是分组结束的标志。
// 由于循环结束后，j=a.length，所以此处也可以写为a[a.length - 1] = i;
a[j - 1] = i;
// 递归调将i-1加入排列
genSetPart(a, i - 1);
// 将排列移动到原来的状态，放入i-1时的状态，以备后续满足条件的排列的调用
for (j = a.length - 1; j >= i; --j) {
a[j] = a[j - 1];
}
} else {
// 打印输出合法的排列
System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args) {
Test_Part.genSetPart(new int[] { 1, 2, 3, 4, 5 }, 5);
}
}
