이 섹션에서는 문자열의 모든 순열을 얻는 방법을 볼 것입니다. 재귀적 접근 방식은 매우 간단합니다. 역추적 절차를 사용합니다. 하지만 여기서는 반복적인 접근 방식을 사용할 것입니다.
문자열 ABC의 모든 순열은 {ABC, ACB, BAC, BCA, CAB, CBA}와 같습니다. 더 나은 아이디어를 얻기 위해 알고리즘을 살펴보겠습니다.
알고리즘
getAllPerm(str)
begin sort the characters of the string while true, do print the string str i := length of str – 1 while str[i - 1] >= str[i], do i := i – 1 if i is 0, then return end if done j := length of str – 1 while j > i AND str[j] <= str[i – 1], do j := j – 1 done exchange the characters from position str[i - 1], str[j] reverse the string. done end
예시
#include <iostream> #include <algorithm> using namespace std; void getAllPerm(string str){ sort(str.begin(), str.end()); while (true){ cout << str << endl; int i = str.length() - 1; while (str[i-1] >= str[i]){ if (--i == 0) return; } int j = str.length() - 1; while (j > i && str[j] <= str[i - 1]) j--; swap(str[i - 1], str[j]); reverse (str.begin() + i, str.end()); } } int main(){ string str = "WXYZ"; getAllPerm(str); }
출력
WXYZ WXZY WYXZ WYZX WZXY WZYX XWYZ XWZY XYWZ XYZW XZWY XZYW YWXZ YWZX YXWZ YXZW YZWX YZXW ZWXY ZWYX ZXWY ZXYW ZYWX ZYXW