如何使用 Steinhaus-Johnson-Trotter (SJT) 算法获取排列 i 并生成第 (i+1)th 排列？有一些解决方案可以使用 SJT 算法生成 all 排列，但由于排列遵循某种模式，我想生成 next 排列。
我尝试写一个这样的算法。然而，对于排列4213，下一个排列应该是2413，但这个程序给出了前一个排列4231。给定 i？，如何生成下一个排列 i+1
public class SJTAlgorithm {
private int[] dir;
// Constructor to initialize the directions
public SJTAlgorithm(int n) {
dir = new int[n];
// Initially, all directions are set to -1 (left).
for (int i = 0; i < n; i++) {
dir[i] = -1;
}
}
// Function to check if an integer is mobile
private static boolean isMobile(int[] permutation, int[] dir, int index) {
int nextIndex = index + dir[index];
// An integer is mobile if the next index is within bounds and
// the adjacent integer in the direction it's moving is smaller.
return nextIndex >= 0 && nextIndex < permutation.length && permutation[index] > permutation[nextIndex];
}
// Function to find the largest mobile integer
private static int getMobileIndex(int[] permutation, int[] dir) {
int mobilePrev = 0, mobileIndex = -1;
for (int i = 0; i < permutation.length; i++) {
if (isMobile(permutation, dir, i) && permutation[i] > mobilePrev) {
mobilePrev = permutation[i];
mobileIndex = i;
}
}
return mobileIndex;
}
// Function to find the next permutation
public static int[] nextPermutation(int[] permutation) {
int n = permutation.length;
int[] dir = new int[n];
// Initially, all directions are set to -1 (left).
for (int i = 0; i < n; i++) {
dir[i] = -1;
}
// Find the largest mobile integer in the permutation.
int mobileIndex = getMobileIndex(permutation, dir);
if (mobileIndex == -1) { // No mobile integer means this is the last permutation.
return null;
}
// Swap the mobile integer with the adjacent integer in its current direction.
int swapIndex = mobileIndex + dir[mobileIndex];
int temp = permutation[mobileIndex];
permutation[mobileIndex] = permutation[swapIndex];
permutation[swapIndex] = temp;
// Change the direction of all integers larger than the current mobile integer.
for (int i = 0; i < n; i++) {
if (permutation[i] > permutation[swapIndex]) {
dir[i] = -dir[i];
}
}
return permutation;
}
// Main function to test the algorithm
public static void main(String[] args) {
int[] permutation = {4, 2, 1, 3};
SJTAlgorithm sjt = new SJTAlgorithm(permutation.length); // Initialize the SJTAlgorithm instance
int[] nextPerm = sjt.nextPermutation(permutation);
if (nextPerm != null) {
System.out.println("Next permutation:");
for (int num : nextPerm) {
System.out.print(num + " ");
}
} else {
System.out.println("No next permutation available (last permutation reached).");
}
}
}
[![enter image description here][1]][1]
[1]: https://i.stack.imgur.com/TajXb.jpg
Steinhaus–Johnson–Trotter (SJT) 算法通过根据每个元素的方向执行一系列交换来生成排列。以下是如何在 C++ 中实现 SJT 算法以生成下一个排列的示例：
#include <iostream>
#include <vector>
#include <algorithm>
// Function to find the largest mobile integer in a given permutation
int findLargestMobile(const std::vector<int>& perm, const std::vector<int>& dir) {
int maxMobile = 0;
int mobileIndex = -1;
const int size = perm.size();
for (int i = 0; i < size; ++i) {
if (((dir[i] == -1) && (i > 0) && (perm[i] > perm[i - 1])) ||
((dir[i] == 1) && (i < size - 1) && (perm[i] > perm[i + 1]))) {
if (perm[i] > maxMobile) {
maxMobile = perm[i];
mobileIndex = i;
}
}
}
return mobileIndex;
}
// Function to generate the next permutation using the Steinhaus–Johnson–Trotter algorithm
void generateNextPermutation(std::vector<int>& permutation) {
int size = permutation.size();
std::vector<int> direction(size, -1); // -1 represents left direction
// Find the largest mobile integer
int mobileIndex = findLargestMobile(permutation, direction);
if (mobileIndex != -1) {
int mobileElement = permutation[mobileIndex];
int dir = direction[mobileIndex];
// Swap the mobile element with the adjacent element in its direction
std::swap(permutation[mobileIndex], permutation[mobileIndex + dir]);
std::swap(direction[mobileIndex], direction[mobileIndex + dir]);
// Reverse the direction of all elements greater than the mobile element
for (int i = 0; i < size; ++i) {
if (permutation[i] > mobileElement) {
direction[i] *= -1;
}
}
}
}
// Function to print a permutation
void printPermutation(const std::vector<int>& permutation) {
for (int num : permutation) {
std::cout << num << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> permutation = {1, 2, 3}; // Change this permutation as needed
std::cout << "Current permutation: ";
printPermutation(permutation);
generateNextPermutation(permutation);
std::cout << "Next permutation: ";
printPermutation(permutation);
return 0;
}
答案：
Current permutation: 4 2 1 3
Next permutation: 4 2 3 1
原因：
Steinhaus–Johnson–Trotter 算法遵循以下结构：它生成的排列序列包括
(n-1)! 排列块，因此每个块内的排列都同意从
1n-1n因此，从一个元素上的单一排列，
1
可以将数字 2 按降序放置在每个可能的位置，以形成两个元素上的两个排列的列表，
1 2
2 1
然后，可以将数字 3 放置在这两个排列的三个不同位置中的每一个中，对于第一个排列 1 2 按降序排列，然后对于排列 2 1 按升序排列：
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3
要了解更多信息，请检查：
时间复杂度
： 使用 Steinhaus–Johnson–Trotter 算法生成下一个排列的时间复杂度为 O(n)，其中 n 是要排列 12 的输入序列的长度。该算法通过仅交换序列中的两个相邻元素来生成序列的所有排列。序列。因此，为了生成下一个排列，我们只需要交换序列中两个相邻的元素即可。 我希望这有帮助！