public class Test5 {
public static void main(String[] args) {
List<Integer> s=new ArrayList<Integer>();
List<Integer> rs=new ArrayList<Integer>();
for(int i=1;i<=4;i++)
s.add(i);
pl(s,rs);
}
public static void pl(List s,List rs){
if(s.size()==1)
{
rs.add(s.get(0));
System.out.println(rs.toString());
rs.remove(rs.size()-1);
}else{
for(int i=0;i<s.size();i++){
rs.add(s.get(i));
List<Integer> tmp=new ArrayList<Integer>();
for(Integer a:s)
tmp.add(a);
tmp.remove(i);
pl(tmp,rs);
rs.remove(rs.size()-1);
}
}
}
}
求大神问一下这段递归是什么意思？，新人表示看不懂
深度优先遍历思想：
for(int ...)
每次从当前剩下的可选数字中选出一个
for(Integer ...)
tmp.add()
tmp.remove
用于挑选出剩下的还未被挑选的数字
pl(tmp, rs)
递归选择下一个数字
rs.remove(rs.size()-1)
rs添加s.get(i)的情况结束，移除最后选择的数字，以运行循环选择另一个不同的数字
说实话这递归写的不怎么样啊，开销很大，逻辑不够清晰。
我写的一个递归解法如下：
public class Sort
{
public static void main(String[] args)
{
int size = 4;
int[] result = new int[size];
int[] status = new int[size];
for(int i = 0; i < size; i++)
{
result[i] = 0;
status[i] = 0;
}
int expect = 1;
for(int i = 2; i <= size; i++)
{
expect *= i;
}
System.out.println("Expect total = "+expect);
int total = sort(result, status, 0);
System.out.println("Real total="+total);
}
/**
* find an available element in status array to fill result[index].
* If index == status.length, result array has been completely filled.So, just print it.
* status[i]=0 means that i is available, status[i]=1 means that i has been used.
*/
public static int sort(int[] result, int[] status, int index)
{
int total = 0;
int len = status.length;
//result has been completely filled, print the array
if(index >= len)
{
for(int i = 0; i < len; i++)
System.out.print(result[i]+" ");
System.out.println();
return 1;
}
//find an avaliable element
for(int i = 0; i < len; i++)
{
//select an available element
if(status[i] != 1)
{
result[index] = i;
status[i] = 1;
//select the next element whose index is (index+1)
total += sort(result, status, index+1);
//finish selected the element whose index is (index+!), release i
status[i] = 0;
}
}
return total;
}
}
建议此类问题不要使用递归解法，因为非递归很容易求解的，而且递归深度太多不太好。下面是一个c实现的非递归解法，由于只使用了数组，JAVA稍加修改(判断数组是否为空的if语句)，应该就可以运行。
基本思想是通过比较，每次调用通过调整位置计算出下个更大的数组
使用方法像这样：
//create and init array a whose size is len
while(next(a, a, len) == 0)
{
//do something you like
}
/**
get the next bigger array
@param dst the array to store the output
@param src the current array
@param n the length of array
@return 0 - ok, -1 - no bigger array than src,
-2 - dst is null
such as:
n = 4
input [1, 2, 4, 3]
output [1, 3, 2, 4]
Note:
If the input array is the largest, the output array will be the same.
Especially, if the input array is null, the output array will
be [1, 2, ..., n].
*/
int next(int dst[], int src[], int n)
{
if(!dst)
return -2;
int i;
if(!src)
{
for(i = 0; i < n; i++)
{
dst[i] = i+1;
}
return 0;
}
else
{
for(i = 0; i < n; i++)
{
dst[i] = src[i];
}
}
//find the larget i which makes a[i-1] < a[i] = true
for(i = n-1; i > 0; i--)
{
if(dst[i-1] < dst[i])
break;
}
//the src is the larget array
if(i == 0)
{
return -1;
}
//now dst[i] >= dst[i+1] >= ... >= dst[n-1]
//reverse dst[i - n-1], make sure dst[i] <= dst[i+1] <= ... <= dst[n-1]
int border = i;
int j = n-1;
int tmp;
for(i = border; i < j; i++, j--)
{
//dst[i] = dst[i+1] = ... = dst[j], no need to reverse
if(dst[i] == dst[j])
break;
//swap dst[i] and dst[j]
tmp = dst[i];
dst[i] = dst[j];
dst[j] = tmp;
}
//find the least i which makes dst[border-1] < dst[i] = true
tmp = dst[border-1];
for(i = border; i < n-1; i++)
{
if(tmp < dst[i])
break;
}
//swap dst[border] and dst[i]
dst[border-1] = dst[i];
dst[i] = tmp;
return 0;
}