Next_Permutation算法

Question

我正在尝试编写一个算法来获得给定的整数数组的下一个排列。我目前的代码只适用于少数输入。因此，我需要帮助找出哪里出了问题。

预期输出仅与最后三个元素的输入不同。因此，我检查了最后三个元素的算法实现。

void Solution::nextPermutation(vector<int> &A) {
    int j, i;
    for (i = A.size() - 1; i > 0; i--) {
        // loop to find i such that A[i-1] < A[i];

        if (A[i - 1] < A[i]) {
            j = i;
            break;
        }
    }

    if (i == 0)
        sort(A.begin(), A.end());
    // to give the lowest order if next_permutation is not possible

    if (i > 0) {
        // if next permutation is possible

        // to swap last element and element at j-1 th index

        if (j == A.size() - 1)
            swap(A[j-1], A[A.size() - 1]);
        else {
            for(int k = A.size() - 1; k >= j; k--) {
                if (A[k] > A[j-1]) {
                    swap(A[k], A[j- 1]);
                    break;
                }
            }
        }

        //to sort the elements after j-1 th index
        sort(A.begin()+j,A.end());
    }

输入：

444,994,701,319,695，52

预期产出：

44,994,701,695，52,319

实际产出：

444 994 701 52 319 695

Answer 1

如果在j-1之后对向量进行排序，则不需要交换。

// Example program
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

void nextPermutation(vector<int> &A) {
    int j,i;
    for(i=A.size()-1;i>0;i--){//loop to find i such that A[i-1]<A[i];
        if(A[i-1]<A[i]){j=i;break;}
    }
    if(i==0){sort(A.begin(),A.end());}
     /*to give the lowest order if  next_permutation 
    is not possible*/


    if(i>0){
        //if next permutation is possible
        //to swap last element and element at j-1 th index
        // swap(A[j-1],A[A.size()-1]);
        //to sort the elements after j-1 th index
        std::sort(A.begin()+j,A.end());
    }
}

int main()
{
    std::vector<int> v= {444, 994,701, 319, 695, 52};
    nextPermutation(v);
    for (int i = 0; i< v.size(); i++) {
        std:: cout << v[i] << "\n";
    }
}

还有一个建议，：您可以完全避免排序。在j+1，.，n中找到k，使得vk是最小的元素> vj，然后旋转向量vj .k-1按顺时针方向一个单位(第一个元素到末尾)。