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

以下是使用Johnson Trotter算法实现生成1到n的全排列的C语言代码：

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

typedef struct {
    int index;
    int *nums;
} Permutation;

int get_mobile(int *nums, int *directions, int n, int *mobile_direction) {
    /* 获取最大可移动元素及其方向 */
    int mobile = -1;
    *mobile_direction = 0;
    for (int i = 0; i < n; i++) {
        int direction = directions[i];
        if (direction == -1 && i > 0 && nums[i] > nums[i-1]) {
            if (mobile == -1 || nums[i] > nums[mobile]) {
                mobile = i;
                *mobile_direction = direction;
            }
        } else if (direction == 1 && i < n-1 && nums[i] > nums[i+1]) {
            if (mobile == -1 || nums[i] > nums[mobile]) {
                mobile = i;
                *mobile_direction = direction;
            }
        }
    }
    return mobile;
}

Permutation *generate_permutations(int n, int *count) {
    int *nums = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    int *directions = (int *) malloc(2 * n * sizeof(int));
    memset(directions, -1, n * sizeof(int));
    memset(directions + n, 1, n * sizeof(int));
    Permutation *permutations = (Permutation *) malloc(factorial(n) * sizeof(Permutation));
    int permutation_index = 1;
    permutations[0].index = permutation_index;
    permutations[0].nums = (int *) malloc(n * sizeof(int));
    memcpy(permutations[0].nums, nums, n * sizeof(int));
    while (permutation_index < factorial(n)) {
        int mobile_direction;
        int mobile = get_mobile(nums, directions, n, &mobile_direction);
        int swap_index = mobile + mobile_direction;
        int temp = nums[mobile];
        nums[mobile] = nums[swap_index];
        nums[swap_index] = temp;
        temp = directions[mobile];
        directions[mobile] = directions[swap_index];
        directions[swap_index] = temp;
        if (mobile_direction == -1) {
            memcpy(permutations[permutation_index].nums, nums, n * sizeof(int));
        } else {
            for (int i = 0; i < n; i++) {
                permutations[permutation_index].nums[i] = nums[n-1-i];
            }
        }
        permutation_index++;
        permutations[permutation_index-1].index = permutation_index;
    }
    free(nums);
    free(directions);
    *count = factorial(n);
    return permutations;
}

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int count;
    Permutation *permutations = generate_permutations(n, &count);
    for (int i = 0; i < count; i++) {
        printf("%d ", permutations[i].index);
        for (int j = 0; j < n; j++) {
            printf("%d", permutations[i].nums[j]);
        }
        printf("\n");
        free(permutations[i].nums);
    }
    free(permutations);
    return 0;
}

输入一个整数n，然后调用`generate_permutations`函数生成1到n的全排列，最后依次输出全排列及其编号。

注意，需要定义一个`Permutation`结构体来保存每个全排列及其编号和具体排列。在生成全排列时，可以利用动态内存分配来保存每个排列，生成完毕后需要手动释放内存。

例如，输入3，输出如下：

1 123
2 132
3 312
4 321
5 231
6 213