Johnson-Trotter(JT)算法生成排列
2024-10-09 06:02:55
对于生成｛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;
}
}
最新文章
- ABP学习日记1
- eclipse的安装环境及eclipse下maven的配置安装
- SharePoint 2010整体进行验证
- OpenLayers3 online build
- JQuery操作Ajax
- 洛谷P1220 关路灯
- Tips--8080端口被占用了怎么办
- java 导出excel(复杂案例)
- beagleboneblack HDMI不能显示
- Mybatis学习（二） - CRUD操作(增删改查操作)
- log 的 debug()、 error()、 info（）方法的区别
- [luogu1402]酒店之王_网络流
- easyui拓展验证结束日期大于等于开始日期
- [转]sqlldr 导入乱码，Oracle客户端字符集问题
- spring cloud+.net core搭建微服务架构：Api授权认证（六）
- 阅读<构建之法>第10、11、12章
- python 类编程相关内容（更新）
- Html5弹幕视频播放器插件
- JAVA 图形开发中组件对齐方法及界面开发
- WebClient 通过get和post请求api