自己手动实现c++ STL中的next_permutation

下面是一个手动实现C++ STL中的next_permutation的示例代码：

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

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

// 反转区间 [first, last) 中的元素
void reverse(int* first, int* last) {
    for (int i = 0; i < (last - first) / 2; i++) {
        swap(&first[i], &last[-i-1]);
    }
}

// 找到区间 [first, last) 中下一个排列，并将其存储在区间 [first, last) 中
int next_permutation(int* first, int* last) {
    if (first == last) return 0;  // 区间为空，返回 false

    int* i = last - 1;  // i 指向最后一个元素
    while (i > first && i[-1] >= i[0]) i--;  // 从后往前找第一个非降序的位置

    if (i == first) {  // 找不到，说明已经是最后一个排列，返回 false
        reverse(first, last);
        return 0;
    }

    int* j = last - 1;  // j 指向最后一个元素
    while (*j <= i[-1]) j--;  // 从后往前找第一个比 i-1 大的元素

    swap(i-1, j);  // 交换 i-1 和 j

    reverse(i, last);  // 反转区间 [i, last)

    return 1;  // 返回 true
}

// 输出区间 [first, last) 中的元素
void print(int* first, int* last) {
    for (int* i = first; i < last; i++) {
        printf("%d ", *i);
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(int);

    do {
        print(arr, arr+n);
    } while (next_permutation(arr, arr+n));

    return 0;
}

该程序的输出结果为：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2