[38] - Permuters

std::rotate, std::shuffle, std::reverse 등등은 여태 공부한 함수와는 다르게 어떤 값을 변화시키지는 않습니다. 임의의 컨테이너[Container] 내의 원소들의 위치를 바꿀 뿐입니다. std::reverse는 말 그대로 컨테이너 내의 원소들의 순서를 반전합니다.

std::reverse

깔끔하며 군더더기 없습니다.

std::shift_left / std::shift_right

자명한 함수입니다. 아쉽게도 C++20 표준이며 현재 사용하는 GCC는 해당 함수를 지원하지 않습니다. 실험을 해볼 수 있는 방법이 다양하게 존재하긴 합니다. (https://en.cppreference.com/w/cpp/algorithm/shift)에 가면 테스트 코드를 실험할 수 있는 컴파일러를 제공합니다. 그런데 이 rotate, shift는 Bit연산에서 배웠던 것과 개념이 닮았습니다.

v of g

std::rotate

shift와 비슷하게 동작할 것 같지만 살짝 다릅니다. 어떻게 동작하는가 하면 먼저 어떤 컨테이너의 범위[Range]를 주고 해당 컨테이너의 첫 번째 index에 오길 바라는 원소의 iterator를 줍니다. 그렇게 하면 입력된 대로 Rotate합니다. 코드와 문서의 원문을 읽으면 이해가 빠릅니다.

어려운 게 없습니다. 물론 컨테이너의 특정 부분만 Rotate하는 것도 가능합니다. 위의 원본의 세 번째(Drei)부터 다섯 번째 원소(Funf)를 포함한 값을 네 번째 원소(Vier)를 가장 앞으로 당길 수 있도록 Rotate 해보겠습니다. 그러면 결과는 

{ Enis Zwei Vier Funf Drei Sechs Seiben Acht Neun Zehn } 이 될 것입니다.

원하는 대로 결과를 받았습니다

std::shuffle / std::random_shuffle

이 함수야 말로 제법 유용하게 활용할 수 있을 것 같습니다. 특히, 게임 같은 요소엔 자주 모습을 보일 것 같습니다. 설명을 읽어보면 무작위로 어떤 컨테이너의 범위 내의 요소들을 섞는다고 되어 있습니다. 우리가 직접 이 Random Function을 지정해 줄 수도 있습니다.

위와 같이 단순하게 컨테이너에 격납된 요소들을 섞을 수 있습니다.

아니면 위와 같이 난수생성 알고리즘을 제작하여 사용할 수도 있습니다. 결과는 무작위로 잘 뽑힙니다.

std::next_permutaion

std::next_permutaion말고도 permutation의 이름을 달고 나온 함수들이 많습니다. 그런데 막상 읽어보면 우리가 수학시간에 접했던 그 permutation을 직관적으로 수행하지는 않습니다. 설명이 좀 난해해서 써보면서 공부하는게 낫습니다.

가령, std::string str { "abcdfeg" };가 있다고 해봅시다. 그리고 std::string은 char의 연속체입니다. 즉, 요소가 char인 컨테이너와 같습니다. 그래서 str에 대해서 std::next_permutation을 수행할 수 있을 것입니다. 그래서 이에 대해 실제로 수행하면 다음과 같은 결과를 얻습니다.

?

상당히 미묘한 결과를 얻었습니다. 위의 한 줄이 원래 상태이고 아래의 줄이 next_permutation을 실시한 결과입니다. 이것은 원래 컨테이너에 격납되어 있던 요소들에 대해서 permutation을 실시했을 때 얻을 수 있는 그 첫 번째 결과입니다. 어떤 결과를 첫 번째로 치부할 수 있는지, 그것은 Lexicographic order에 따릅니다. 즉, 사전에 이들을 싣게 되었을 때 나타나는 순서를 일컫습니다.

그러면 실제로 이 함수를 계속 호출하면 Lexicograhic Order대로 인쇄가 될까요? 이것을 실행에 옮겨보기 위해서는 약간의 직관이 필요한데, 이 std::next_permutaion함수는 반환형이 Boolean입니다. 그러면, 직관적으로 이 함수는 State를 갖고 어떤 최종 결과에 와서 모든 결과에 대해 다른 결과를 내놓으면서 끝날 것입니다. 다음과 같이 짜보면 잘 됩니다. 그리고 실제로 호출될 때마다 다음 permutation값을 내놓습니다.

근데 결과가 너무 방대해서 모두 담을 수 없습니다. 6P6 = 6!입니다. 제법 큰 수입니다. std::prev_permutaion도 존재하는데 이는 순서를 뒤집은 결과를 줍니다. 또 알아두면 좋을 특징이 하나 있는데, 이 std::permutation계열의 함수들은 연속된 요소에 대해서는 위치가 바뀌어도 같은 하나로 취급합니다. 즉, { a, b, b, b }의 permutation의 결과는 다음과 같습니다.

Permutation은 Coding Test에서 자주 만나는 문제이기도 합니다. 크게 어렵지 않은 구현이기 때문에 개념은 이해하고 사용하는 편이 좋습니다.