【问题描述】给定正整数n生成1到n的全排列（利用Johnson Trotter算法） 【输入形式】一个整数n（1<=n<=9） 【输出形式】n!行，每一行的第一个数是第几个全排列，第二个数是全排列打印 3 【样例输入】 1123 2132 3312 4321 5231 6213 用C语言实现

好的，我可以给你提供一个 C 语言实现的 Johnson Trotter 算法来生成 1 到 n 的全排列。以下是实现的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义全局变量
int *p;   // 存放全排列的数组
int *dir; // 存放每个元素的方向，1 表示向右，-1 表示向左

// 初始化全排列和方向数组
void init(int n) {
    // 分配内存空间
    p = (int *)malloc(n * sizeof(int));
    dir = (int *)malloc(n * sizeof(int));

    // 初始化全排列为 1, 2, ..., n
    for (int i = 0; i < n; i++) {
        p[i] = i + 1;
        dir[i] = -1; // 初始方向都向左
    }
}

// 打印全排列
void print_permutation(int n, int count) {
    printf("%d ", count);
    for (int i = 0; i < n; i++) {
        printf("%d", p[i]);
    }
    printf("\n");
}

// 交换数组中的两个元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 执行 Johnson Trotter 算法，生成全排列
void johnson_trotter(int n) {
    int count = 1; // 记录第几个全排列
    while (1) {
        print_permutation(n, count); // 打印全排列
        count++; // 全排列计数加 1

        // 找到最大的可以移动的元素
        int mobile = -1;
        int mobile_idx = -1;
        for (int i = 0; i < n; i++) {
            if ((dir[i] == -1 && i > 0 && p[i] > p[i-1]) ||
                (dir[i] == 1 && i < n-1 && p[i] > p[i+1])) {
                if (p[i] > mobile) {
                    mobile = p[i];
                    mobile_idx = i;
                }
            }
        }

        // 如果没有可以移动的元素，说明全排列已经生成完毕，退出循环
        if (mobile_idx == -1) {
            break;
        }

        // 移动最大的可以移动的元素
        if (dir[mobile_idx] == -1) {
            swap(&p[mobile_idx], &p[mobile_idx-1]);
            swap(&dir[mobile_idx], &dir[mobile_idx-1]);
        } else {
            swap(&p[mobile_idx], &p[mobile_idx+1]);
            swap(&dir[mobile_idx], &dir[mobile_idx+1]);
        }

        // 翻转所有比 mobile 大的元素的方向
        for (int i = 0; i < n; i++) {
            if (p[i] > mobile) {
                dir[i] = -dir[i];
            }
        }
    }

    // 释放内存空间
    free(p);
    free(dir);
}

int main() {
    int n;
    scanf("%d", &n);
    init(n);
    johnson_trotter(n);
    return 0;
}

以上代码中，我们定义了一个 `init` 函数来初始化全排列和方向数组，定义了一个 `print_permutation` 函数来打印全排列，定义了一个 `swap` 函数来交换数组中的两个元素，定义了一个 `johnson_trotter` 函数来执行 Johnson Trotter 算法，最后在 `main` 函数中调用这些函数来生成全排列。