C语言找到上一个排列

在C语言中，找到一个整数数组的上一个排列通常涉及到生成所有可能的排列，并在其序列中向前搜索。这里我们使用了经典的“next permutation”算法，它是从当前排列开始逆序查找第一个逆序对，然后交换这个对并顺次将右边的所有元素移到左边以形成下一个排列。

以下是一个基本的实现，假设数组已排序（从小到大），并且我们知道如何通过比较元素来判断一个排列是否是另一个排列的前一个：

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

bool compare(const void *a, const void *b) {
    return (*(int*)a) > (*(int*)b);
}

void find_prev_permutation(int arr[], size_t n, int *index) {
    int last_descending_index = -1;

    // 找到最后一个下降的元素
    qsort(arr, n, sizeof(arr[0]), compare);
    for (size_t i = n - 1; i > 0; i--) {
        if (arr[i] > arr[i - 1]) {
            last_descending_index = i - 1;
            break;
        }
    }

    if (last_descending_index == -1) {
        printf("No previous permutation exists.\n");
        return;
    }

    // 寻找小于当前元素的最大值
    int max_index = -1;
    for (size_t i = last_descending_index + 1; i < n; i++) {
        if (arr[i] > arr[last_descending_index]) {
            max_index = i;
        }
    }

    // 交换元素
    int temp = arr[last_descending_index];
    arr[last_descending_index] = arr[max_index];
    arr[max_index] = temp;

    // 将剩余元素倒序
    for (size_t i = n - 1, j = last_descending_index + 1; i >= j; i--, j++) {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    *index = last_descending_index;
}

int main() {
    int arr[] = {1, 4, 2, 3};
    int index = -1;
    find_prev_permutation(arr, sizeof(arr) / sizeof(arr[0]), &index);

    printf("The previous permutation of [1, 4, 2, 3] is [");
    for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
        printf("%d ", arr[i]);
    }
    printf("] at position %zu\n", index + 1); // Index starts from 0

    return 0;
}

这个程序会先找到最后一个下降的元素，然后找到比它小的最大元素，并将它们互换。接着，剩余的部分会被反转，以生成上一个排列。注意，这个方法假设数组不是完全升序的，因为如果是完全升序的话就没有前一个排列。