STJ算法是什么

2023-08-01 10:28:00 生活常识 投稿:软馨吖

SJT算法是一种全排列生成算法。在该算法中,不断的寻找一种相邻元素相互交换的顺序,根据这种交换的顺序,依次计算下一个排列。该算法的算数复杂度是O(n*n!)。

SJT 算法,即 Steinhaus–Johnson–Trotter algorithm,是一种全排列生成算法。在该算法中,不断的寻找一种相邻元素相互交换的顺序,根据这种交换的顺序,依次计算下一个排列。该算法的算数复杂度是 O(n*n!)。

STJ算法是什么

算法原理

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!)。

标签: # 算法 # STJ
声明:犀牛文库所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系admin@qq.com