解决组合排列问题 A (m ,n) m>=n

转载自http://blog.csdn.net/sunyujia/article/details/4124011

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* <p>
* Title:全排列算法
*/
public class FullSort {
//将NUM设置为待排列数组的长度即实现全排列
private static int NUM = 3;

/**
* 递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列
*/
private static void sort(List datas, List target) {
if (target.size() == NUM) { //if{}实现输出
for (Object obj : target)
System.out.print(obj);
System.out.println();
return;
}
for (int i = 0; i < datas.size(); i++) {
List newDatas = new ArrayList(datas);
List newTarget = new ArrayList(target);
newTarget.add(newDatas.get(i));
newDatas.remove(i);
sort(newDatas, newTarget);//递归调用
}
}

public static void main(String[] args) {
String[] datas = new String[] { "a", "b","c","d" };
sort(Arrays.asList(datas), new ArrayList());
}

}

结果：

abc
abd
acb
acd
adb
adc
bac
bad
bca
bcd
bda
bdc
cab
cad
cba
cbd
cda
cdb
dab
dac
dba
dbc
dca
dcb

文字分析：对ABCD中去三个数排列

abcd

（第一层）第一次调用sort(abcd,空值）函数时 target.size=0 进入for循环此时 i=0 newTarget=a newData=bcd,调用sort(bcd,a);
(第二层)target.size=1 ！=num 进入for循环 i=0 newTarget=ab newData=cd 调用sort(cd,ab)
(第三层) target.size=2 ！=num 进入for循环 i=0 newTarget=abc newData=d 调用sort(d,abc)
(第四层) target.size=3 =num 输出 abc 在返回第三层

(第三层）进入for循环 i=1 newTarget=abd newData=c 调用sort(abd,c)
(第四层) target.size=3 =num 输出 abd 在返回第三层
(第三层) for循环结束返回第二层
（第二层）进入for循环 i=1 ewTarget=ac newData=bd 调用sort(ac,bd)

等 ----

图示：

巴特西

解决组合排列问题 A (m ,n) m>=n

最新文章

热门文章