std::next_permutation 알고리즘은 사전순으로 더 큰 시퀀스 순열을 찾기 위해 어떻게 작동합니까?

std::next_permutation 구현 설명

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

알고리즘 개요

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

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

가변 역할

• i: 현재 검사 중인 요소.
• j: 포인트 i 바로 앞의 요소.
• k: i가 어센더인 경우 i 오른쪽에 있는 시퀀스에서 가장 작은 요소를 가리킵니다.

루프 흐름

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

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

예

수열 {1, 2, 4, 3}을 생각해 보세요.

• 반복 1: i는 처음에 3입니다. j는 2입니다. 이후 3입니다. < 4 (i
• 반복 2: k는 2입니다. 3은 2로 교환됩니다. {1, 3, 4, 2} . 3의 오른쪽에 있는 요소(4와 2)가 반전됩니다. {1, 3, 2, 4}.
• 반복 3: i는 감소하고 j는 감소합니다. i는 이제 2에 있습니다. j는 1에 있습니다. 2 < 3이므로 i는 어센더입니다.
• 반복 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}.

위 내용은 std::next_permutation 알고리즘은 사전순으로 더 큰 시퀀스 순열을 찾기 위해 어떻게 작동합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!