对于生成{1,……,n}的所有n!个排列的问题,我们可以利用减治法,该问题的规模减一就是要生成所有(n-1)!个排列。假设这个小问题已经解决了,我们可以把n插入到n-1个元素的每一种排列中的n可能的位置中去,来得到较大规模大问题的一个解。按照这种方式生成的所有排列都是独一无二的,并且他们的总数应该是n(n-1)!=n!。这样,我们都得到了{1,……,n}的所有排列。
JohnsonTrotter算法实现形式。
JohnsonTrotter(n)
输入:一个正整数n
输出:{1,……,n}的素有排列的列表
将第一个排列初始化为方向向左的元素数组
while 存在一个移动元素k do
求最大的移动元素k
把k和它箭头指向的相邻元素互换
调转所有大于k的元素的方向
将新排列添加到列表
(摘自算法设计与分析基础)
下午自己实现了一下这个算法,将其改成可以把N个不重复的元素排列出来,程序中使用到的比较器提供接口需要自己去实现,程序运行需要把使用者自己实现的比较器注入程序。自我感觉程序灵活性还可以。
/**
* 使用JT算法进行排列组合。
* 注意:请务必保持范型和比较接口范型一致,否则可能产生不可预知的错误
* @author LiuYeFeng<897908343@qq.com>
* @date 2015年4月9日 下午5:31:00
* @CopyRight 2015 TopView Inc
* @version V1.0
* @param <E> 需要排列的元素的范型,请务必保持范型和比较接口范型一致,否则可能产生不可预知的错误
*/
public class JTAlgorithm<E>{
//存放排列元素的数组
protected E[] array;
//元素的方向数组
private Direction[] directions;
//比较器,用于比较元素大小
private Compare<E> compare;
public JTAlgorithm(Class<? extends Compare<E>> clazz) {
//获取比较方法的实例
this.compare = (Compare) ReflectUtils.newInstance(clazz);
}
public JTAlgorithm(Compare<E> compare) {
//获取比较方法的实例
this.compare = compare;
}
public List<E[]> generate(E[] elements) {
List<E[]> result = new ArrayList<E[]>();
//初始化工作
init(elements);
//最大可移动元素的位置
int biggestFlag = findBiggestMobileElement();
//自身也为一种排列
result.add(Arrays.copyOf(array, array.length));
//存在可移动最大元素k
while (biggestFlag != -1) {
//将k和箭头指向的相邻元素互换
biggestFlag = changeBiggestElementAndNeighbor(biggestFlag);
//调转所有大于k的元素的方向
changeDirection(biggestFlag);
//将新排列添加到结果集
result.add(Arrays.copyOf(array, array.length));
//重新查找可移动最大元素
biggestFlag = findBiggestMobileElement();
}
return result;
}
private void init(E[] elements) {
//用快排把元素排序
QuickSort<E> qk = new QuickSort<E>(compare);
qk.sort(elements, 0, elements.length - 1);
array = elements;
directions = new Direction[array.length];
//初始化方向
for (int i = 0; i < directions.length; i++) {
directions[i] = Direction.LEFT;
}
}
/**
* 把比loc位置大的元素的方向反转
* @param loc
*/
private void changeDirection(int loc) {
for (int i = 0; i < array.length; i++) {
if (compare.greaterThan(array[i], array[loc])) {
directions[i] = (directions[i] == Direction.LEFT) ? Direction.RIGHT : Direction.LEFT;
}
}
}
/**
* 把loc元素和它的邻居互换,并把互换后loc的新位置返回
* @param loc
* @return loc的新位置
*/
private int changeBiggestElementAndNeighbor(int loc) {
int neighbor = -1;
if (directions[loc] == Direction.LEFT) {
neighbor = loc - 1;
} else {
neighbor = loc + 1;
}
E temp = array[loc];
array[loc] = array[neighbor];
array[neighbor] = temp;
Direction dTemp = directions[loc];
directions[loc] = directions[neighbor];
directions[neighbor] = dTemp;
return neighbor;
}
/**
* 查找最大可移动元素
* @return 最大可移动元素的位置
*/
private int findBiggestMobileElement() {
int loc = -1;
int biggestLoc = -1;
for (int i = 0; i < array.length; i++) {
//判断左右方向
if (directions[i] == Direction.LEFT) {
//如果是头元素,则无法向左比较,跳过
if (i == 0) {
continue;
}
if (compare.greaterThan(array[i], array[i - 1])) {
loc = i;
}
} else {
//如果是尾元素,则无法向右比较,跳过
if (i == array.length - 1) {
continue;
}
if (compare.greaterThan(array[i], array[i + 1])) {
loc = i;
}
}
//如果第一次找到可移动元素,则把最大可移动元素改变,之后把本次找到的可移动元素和最大可移动元素进行比较
if (loc != -1 && biggestLoc == -1) {
biggestLoc = loc;
}else if (biggestLoc != -1 && compare.greaterThan(array[loc], array[biggestLoc])) {
biggestLoc = loc;
}
}
return biggestLoc;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)