c++ 함수 next_permutation이 순열을 건너 뛰는 이유는 무엇입니까?



next_permutation 함수 (4)

왜이 간단한 함수는 입력 된 5 글자 문자열의 모든 순열을 출력하지 않습니까? 나는 120이 있어야한다고 생각하고 90을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// Creates permutation lists for strings
vector<string> createdcombos2(string letters)
{ 
    vector<string> lettercombos;    

    cout << "Letters are: " << letters << endl; //input string

    do 
        lettercombos.push_back(letters);        
    while(next_permutation(letters.begin(), letters.end()));    

    cout <<"Letter combos: " << endl;  //print out permutations 
    for (auto i : lettercombos)
        cout << i << endl;
    cout << endl << lettercombos.size() << endl; //number of permutations

    return lettercombos;
}


int main() 
{
    string letters = "gnary"; 
    vector<string> lettercombos;

    lettercombos = createdcombos2(letters);
}

이전에 만들어진 답변의 std::next_permutationbool 반환 값을 사용하여 반복을 중지하려면 "정렬 된"순열에서 시작해야합니다. 그렇지 않으면주기가 너무 일찍 종료됩니다.

그러나 이것은 꼭 필요한 것은 아닙니다.

std::next_permutation 통해 열거 된 순열은 시작이나 끝이없는 순환 순서 를 형성합니다. 즉, std::next_permutation 무기한 호출 할 수 있으며 다시 120 순열의 동일한 시퀀스를 반복합니다. 이것은 당신이 그 사이클에서 절대적으로 순열을 시작할 수 있음을 의미합니다. 시작 순열을 기억하고이 순열이 다시 나타나는 순간을 지켜봐야합니다. 원래 순열에 도착한 순간 반복이 끝났습니다. 귀하의 경우에는 예상대로 std::next_permutation 호출이 120 번 걸릴 것입니다.

예를 들어, 다음 코드는 "abcde" 대한 모든 5 문자 순열을 완전히 임의의 것으로부터 시작하더라도 설정합니다

std::string start = "cadeb", current = start;
do
  std::cout << current << std::endl;
while (std::next_permutation(current.begin(), current.end()), current != start);

순환의 각 반복에서 순열을 비교하는 것이 std::next_permutation (알고리즘의 내부에서 "무료"로 std::next_permutation 의 반환 값을 사용하는 것보다 비용이 많이 들지만 솔루션에 만족하면 사전 순열을 미리 정렬하면 실제로는보다 효율적으로 수행 할 수 있습니다.

또는 사이클의 순열 수 (이 경우 120)를 알고 있으면 std::next_permutation 해당 횟수만큼 호출하면됩니다 (@ Potatoswatter의 답변에서 제안 된 것처럼).


next_permutation이 false를 반환 할 때까지 모든 순열을 루프에서 반환하려면 벡터가 루프 시작 전에 정렬되어야합니다. next_permutation 은 순열을 오름차순으로 반환합니다. 따라서 정렬되지 않은 벡터로 시작하면 일련의 순열을 통해 부분적으로 시작됩니다.

std::sort(letters.begin(), letters.end());
do 
    lettercombos.push_back(letters);        
while(next_permutation(letters.begin(), letters.end()));  

입력을 정렬해야 할 경우 next_permutation 은 사전 순으로 다음 순열을 반환합니다. 입력 순열 : "gnary""화난" 과 같은 순열보다 사전 적으로 "더 크다"때문에, "더 작은"순열에 도달하지 않습니다.

std::sort() 사용하여 문자열을 정렬 할 수 있습니다.


next_permutation 의 반환 bool 값은 오버플로 조건 또는 캐리 비트와 같습니다. 그것은 마지막 순열에서부터 최초 순차 순서로 되돌아 갈 때 false 입니다. 그러나 그것은 여전히 ​​무조건 전진합니다.

정확하게 120 개의 순열이 있다는 것을 알고 있다면 반환 값을 무시하고 맹목적으로 루프 할 수 있습니다.

for ( int i = 0; i != 120; ++ i ) {
    lettercombos.push_back(letters);        
    next_permutation(letters.begin(), letters.end());
}




permutation