SJT算法是一种全排列生成算法。在该算法中,不断的寻找一种相邻元素相互交换的顺序,根据这种交换的顺序,依次计算下一个排列。该算法的算数复杂度是O(n*n!)。
SJT 算法,即 Steinhaus–Johnson–Trotter algorithm,是一种全排列生成算法。在该算法中,不断的寻找一种相邻元素相互交换的顺序,根据这种交换的顺序,依次计算下一个排列。该算法的算数复杂度是 O(n*n!)。
算法原理
SJT 算法,即 Steinhaus–Johnson–Trotter algorithm,是一种全排列生成算法。在该算法中,不断的寻找一种相邻元素相互交换的顺序,根据这种交换的顺序,依次计算下一个排列。在 SJT 算法中,每次循环都进行一次满足条件的相邻元素的交换,直到不存在满足条件的可交换的元素,此时说明所有排列的情况均已输出,算法结束。
算法步骤
设[a1,a2 … aN] 每一项都有向左或向右两个移动方向。
1) 初始化所有移动方向向左;
2) 如果移动方向的值比自己小,就可移动,比如 <1 >2 <3, 每个数字前箭头的方向表示该数字的移动方向,3 可以移动,2 和 1 不可移动;
3) 移动最大的可以动项,在上面例子中就是数字 3;
4) 将所有比移动项大的项方向反转,重复第三步,直到不能移动为止。
算法性能分析
记要全排列的元素总数为 n,全排列一共 n!种排列,在每次枚举下一个排列时,我们都在上一个排列中寻找最大的可移动项,然后对其进行移动,因此总体复杂度是 O(n*n!)。