Permutation

• 순열 $\frac{n!}{(n-r)!}$
  • for → 이전 index와 != 경우만
  • 원소의 순서가 중요
    • {1, 2}와 {2, 1}은 다르다
    • 체크배열 순회 (for문은 항상 0부터)
    • 타겟 순열 사이즈
    • 재귀 함수 depth
      • 재귀 호출시 depth + 1
• next_permutation with sort

  •       vector<char> set = {'A', 'B', 'C', 'D'};
          
          do {
              for (char c : set) {
                      cout << c << " ";
              }
              cout << endl;
          } while (next_permutation(set.begin(), set.end())); 

• recursive
  • logic
    • 소스 배열
    • 체크 배열
    • 현재 배열
    • 타겟 순열 크기
    • 종료 조건
      • 현재 배열 타겟 길이 체크

  •   #include <iostream>
      #include <vector>
      
      using namespace std;
      
      void permute(vector<int>& arr, vector<bool>& used, vector<int>& current, int depth) {
      
          if (depth == arr.size()) {
              for (int num : current) cout << num << " ";
              cout << "\n";
              return;
          }
      
          for (int i = 0; i < arr.size(); i++) {
              if (!used[i]) {
                  used[i] = true;
                  current.push_back(arr[i]);
                  permute(arr, used, current, depth + 1);
                  current.pop_back();
                  used[i] = false;
              }
          }
      }
      
      int main() {
          vector<int> arr = {1, 2, 3};
          vector<bool> used(arr.size(), false);
          vector<int> current;
      
          permute(arr, used, current, 0);
      
          return 0;
      }