johnson-trotter算法C++实现

Johnson-Trotter 算法是一种用于生成排列的算法，主要用于解决置换问题，即产生一个给定数目的元素的所有排列。该算法基于一种称为“字典序”的概念，它按照字典中单词的顺序生成所有可能的排列。Johnson-Trotter 算法具有线性的时间复杂度，这使得它在实际应用中非常高效。

以下是该算法的C++实现的核心步骤：

1. 初始化一个从1到n的整数数组，表示当前排列。
2. 在每一步中，找到当前排列中可以从左向右或从右向左移动的最大数（即最右边的可以移动的数）。
3. 交换这个数和它左边或右边的数，取决于哪边可以移动。
4. 如果一个数移动到了边界，就将其标记为“固定”。
5. 重复步骤2到4，直到没有可以移动的数为止。

这里是一个简化的C++实现示例：

#include <iostream>
#include <vector>
using namespace std;

void swap(vector<int>& nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void printPermutation(const vector<int>& nums) {
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
}

void JohnsonTrotter(vector<int>& nums) {
    int n = nums.size();
    int dir = 1; // Direction to move: 1 for right, -1 for left
    int maxIndex;

    while (true) {
        maxIndex = -1;

        // Find the largest number in nums that can be moved in the current direction
        for (int i = 0; i < n; ++i) {
            if (dir == 1 && i + 1 < n && nums[i] > nums[i + 1]) {
                maxIndex = i;
            } else if (dir == -1 && i - 1 >= 0 && nums[i] > nums[i - 1]) {
                maxIndex = i;
            }
        }

        if (maxIndex == -1) {
            break; // No more permutations
        }

        // Swap the largest number with the number in the direction to move
        swap(nums, maxIndex, maxIndex + dir);

        // Print the permutation
        printPermutation(nums);

        // Toggle the direction for the next iteration
        dir = -dir;
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    JohnsonTrotter(nums);
    return 0;
}

这段代码是一个Johnson-Trotter算法的简化版本，它输出了从1到4的所有排列。它使用了一个`vector<int>`来存储当前排列，并通过改变数字的顺序来生成下一个排列。