找到前N个自然数的好排列 C++

何为好排列

好的排列是指排列中没有升降沟，而降升沟数等于排列中逆序对个数的排列。

举个例子，排列5 2 4 3 1，其升降沟数为3，逆序对个数为8，因此它不是好排列。

在实现找到前N个自然数的好排列时，需要使用到“逆序对”这一概念。

逆序对

定义

在一个数组中，如果前面的数大于后面的数，那么这两个数构成一个逆序对。

例如，数组[7,5,6,4]中，(7,5)、(7,6)、(7,4)、(5,4)、(6,4)都是逆序对。

求逆序对

常见的求逆序对的方法有暴力枚举和归并排序。

下面介绍归并排序的方法，其时间复杂度为O(nlogn)。

void merge(vector& nums, int left, int mid, int right, long long& count) {
    vector temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while(i <= mid && j <= right) {
        if(nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            count += mid - i + 1; // 统计逆序对数
            temp[k++] = nums[j++];
        }
    }
    while(i <= mid) temp[k++] = nums[i++];
    while(j <= right) temp[k++] = nums[j++];
    for(int p = 0; p < temp.size(); ++p) {
        nums[left + p] = temp[p];
    }
}
void mergeSort(vector& nums, int left, int right, long long& count) {
    if(left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid, count);
    mergeSort(nums, mid + 1, right, count);
    merge(nums, left, mid, right, count);
}
long long countPairs(vector& nums) {
    long long count = 0;
    mergeSort(nums, 0, nums.size() - 1, count);
    return count;
}

找到前N个自然数的好排列

思路

首先，定义一个数组a，将前n个自然数存放在a中。

接着，我们需要去枚举a数组的所有全排列。

对于每个排列，我们都要判断其是否是好排列，如果是，则将其加入结果数组中。

最后，取结果数组中前N个好排列输出即可。

代码实现

vector> res;
bool isGood(vector& nums) { // 判断是否为好排列
    int len = nums.size(), up = 0, down = 0;
    vector dp(len, 1);
    for(int i = 1; i < len; ++i) {
        for(int j = 0; j < i; ++j) {
            if(nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
                up = max(up, dp[i]);
            } else if(nums[i] < nums[j]) {
                down++;
            }
        }
    }
    return down == (len * (len - 1) / 2 - up);
}
void dfs(vector& nums, int depth) {
    if(depth == nums.size()) {
        if(isGood(nums)) res.push_back(nums);
        return;
    }
    for(int i = depth; i < nums.size(); i++) {
        swap(nums[i], nums[depth]);
        dfs(nums, depth + 1);
        swap(nums[i], nums[depth]);
    }
}
vector> findGoodPermutation(int n, int k) {
    vector nums(n);
    for(int i = 0; i < n; ++i) {
        nums[i] = i + 1;
    }
    dfs(nums, 0);
    sort(res.begin(), res.end(), [](vector& x, vector& y) {
        for(int i = 0; i < x.size(); ++i) {
            if(x[i] == y[i]) continue;
            return x[i] < y[i];
        }
        return true;
    });
    return vector>(res.begin(), res.begin() + k);
}

总结

本文主要介绍了如何找到前N个自然数的好排列。在实现过程中，我们需要用到“逆序对”这一概念，而求逆序对的方法有暴力枚举和归并排序。另外，我们还需要枚举全排列，并判断其是否为好排列，最后取前N个输出即可。

该算法时间复杂度较高，因为要枚举所有排列并判断其是否为好排列。可能存在优化方法，但笔者目前还未有更好的思路。如果您有更好的优化方法，欢迎在评论区留言分享。