순열

 

 

 

순서가 필요한 경우 다음 참고하여 빠르게 구현하도록 한다.

 

next_permutation 함수:

C++ 표준 라이브러리의 <algorithm> 헤더에 있는 next_permutation 함수는 순열(Permutation)을 생성하기 위해 사용됩니다.

 

next_permutation 함수는 현재 순열을 기준으로 다음 순열을 생성하고, 순열이 더 이상 존재하지 않을 때는 false를 반환합니다.

 

int main() {

    int a[] = {1,2,3};

    do{
        for(int i : a) cout << i << " ";
        cout << '\n';
    } while (next_permutation(a, a + 3));
}

 

아래는  next_permutation 함수를 사용하여 배열의 모든 순열을 생성하는 과정을 도식화한 것입니다.

초기 배열: [1, 2, 3]

1. 현재 배열 [1, 2, 3] 출력

2. 다음 순열 생성을 위해 next_permutation 호출
   - 배열 [1, 2, 3]을 기준으로 다음 순열을 생성
   - 다음 순열 [1, 3, 2] 반환, true 반환

3. 현재 배열 [1, 3, 2] 출력

4. 다음 순열 생성을 위해 next_permutation 호출
   - 배열 [1, 3, 2]을 기준으로 다음 순열을 생성
   - 다음 순열 [2, 1, 3] 반환, true 반환

5. 현재 배열 [2, 1, 3] 출력

6. 다음 순열 생성을 위해 next_permutation 호출
   - 배열 [2, 1, 3]을 기준으로 다음 순열을 생성
   - 다음 순열 [2, 3, 1] 반환, true 반환

7. 현재 배열 [2, 3, 1] 출력

8. 다음 순열 생성을 위해 next_permutation 호출
   - 배열 [2, 3, 1]을 기준으로 다음 순열을 생성
   - 다음 순열 [3, 1, 2] 반환, true 반환

9. 현재 배열 [3, 1, 2] 출력

10. 다음 순열 생성을 위해 next_permutation 호출
    - 배열 [3, 1, 2]을 기준으로 다음 순열을 생성
    - 다음 순열 [3, 2, 1] 반환, true 반환

11. 현재 배열 [3, 2, 1] 출력

12. 다음 순열 생성을 위해 next_permutation 호출
    - 배열 [3, 2, 1]을 기준으로 다음 순열을 생성
    - 다음 순열 [1, 2, 3] 반환, false 반환

모든 순열 생성 완료

위의 도식화된 예시에서는 초기 배열 `[1, 2, 3]`을 시작으로 next_permutation 함수를 호출하여 다음 순열을 생성하고 출력합니다. 이 과정을 배열의 모든 순열을 생성할 때까지 반복합니다. 

 

마지막에 next_permutation 함수는 false를 반환하여 순열 생성을 종료합니다.

순열의 생성은 배열의 요소들을 모든 가능한 순서로 재배치하는 과정이며, next_permutation 함수를 사용하면 간편하게 모든 순열을 생성할 수 있습니다.

 

* tip

 c++11 도입된 for-each 루프 혹은 range-based for loop 인 for(int :i :a)와 같은 형태의 문법이 있다.

 

해당 문법은 배열, 벡터, 리스트 등과 같은 각 요소를 순차적으로 접근하기 위해 단순하고 간결한 방법을 제공한다. 

 

for(int i : a)

 

위 예시에서 a는 컨테이너를 나타내며, int it는 각 요소를 참조할 변수를 나타낸다. 

 

실제로 컨테이너의 인덱스나 크기를 사용하지 않아 매우 간결한 가독성을 제공해준다는 점이 특징이다.