std::next_permutation 구현 설명

std::next_permutation 알고리즘은 주어진 시퀀스의 사전순으로 더 큰 다음 순열을 계산합니다. 동작을 이해하려면 구현을 이해하는 것이 중요합니다.

알고리즘 개요

알고리즘은 오른쪽에서 왼쪽으로 시퀀스를 반복하여 가장 왼쪽의 "오름차순"(예: , 후속 요소보다 작은 요소). 어센더가 발견되지 않으면 시퀀스가 ​​내림차순임을 의미하며, 이 경우 시퀀스를 뒤집어 가장 작은 순열을 얻습니다.

그렇지 않으면 알고리즘은 오른쪽 시퀀스에서 가장 작은 요소를 찾는 방식으로 계속됩니다. 어센더("k"라고 함). 그런 다음 이 요소는 어센더로 교체됩니다. 마지막으로, 내림차순을 유지하기 위해 어센더 오른쪽에 있는 요소가 반전됩니다.

가변 역할

• i: 다음을 가리킵니다. 검사 중인 현재 요소.
• j: i 바로 앞의 요소를 가리킵니다.
• k: 시퀀스에서 가장 작은 요소를 가리킵니다. i가 어센더일 때 i의 오른쪽에 있습니다.

루프 흐름

루프는 i가 시퀀스의 시작(시작)에 도달할 때까지 반복됩니다. 각 반복 내에서:

1. i가 어센더가 아닌 경우 i와 j가 감소합니다.
2. i가 어센더인 경우 i 오른쪽에 있는 가장 작은 요소를 찾습니다(k ), i와 교환하고 i의 오른쪽에 있는 모든 항목을 반대로 바꿉니다.

예

수열 {1, 2, 4, 3}을 고려하세요. .

• 반복 1: i는 처음에 3입니다. j는 2입니다. 3
• 반복 2: k는 2로 밝혀졌습니다. 3은 2로 교체되었습니다. {1, 3, 4, 2}. 3의 오른쪽에 있는 요소(4와 2)가 반전됩니다. {1, 3, 2, 4}.
• 반복 3: i는 감소하고 j는 감소합니다. i는 현재 2입니다. j는 1. 2
• 반복 4: k는 1입니다. 2는 1로 교환됩니다. { 1, 2, 4, 3}. 2의 오른쪽에 있는 요소(4와 3)가 반전됩니다. {1, 2, 3, 4}.
• 반복 5: i는 감소하고 j는 감소합니다. i는 이제 1에 있습니다. j는 시퀀스의 시작 부분에 있습니다. 더 이상 어센더가 없으므로 순서가 반대가 됩니다. {4, 3, 2, 1}.