C++의 순열 시퀀스

<시간/>

집합이 [1,2,3,...,n]과 같으며 총 n을 포함한다고 가정합니다! 독특한 순열. 모든 순열을 순서대로 나열하고 레이블을 지정하면 n =3에 대해 다음 시퀀스를 얻습니다. ["123","132","213","231","312","321"] 따라서 n과 k가 주어진 다음 k 번째 순열 시퀀스를 반환합니다. n은 1에서 9(포함) 사이이고 k는 1에서 n 사이입니다! (포함한). 예를 들어 n =3인 경우.

단계를 살펴보겠습니다 -

ans :=빈 문자열, 크기가 n인 후보라는 배열 정의
0 ~ n – 1 범위의 i에 대해
- 후보[i] :=((i + 1) + 문자 '0')
크기가 n + 1인 팩트라는 배열 하나를 만들고 팩트[0] :=1로 설정
1~n
- 사실[i] :=사실[i – 1] * 나
k를 1 감소
i:=n – 1에서 0까지
- idx :=k / 사실[i]
- ans :=ans + 후보자[idx]
- for j :=idx, j + 1 <후보 크기
  - 후보[j] :=후보자[j + 1]
- k :=k 모드 팩트[i]
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   string getPermutation(int n, int k) {
      string ans = "";
      vector <char> candidates(n);
      for(lli i = 0; i < n; i++)
         candidates[i] = ((i + 1) + '0');
      vector <lli> fact(n + 1);
      fact[0] = 1;
      for(lli i = 1; i <= n; i++)
         fact[i] = fact[i - 1] * i;
      k--;
      for(lli i = n - 1; i >= 0; i--){
         lli idx = k / fact[i];
         ans += candidates[idx];
         for(lli j = idx; j + 1< candidates.size(); j++)
            candidates[j] = candidates[j + 1];
         k = k % fact[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << ob.getPermutation(4, 9);
}

입력

4
9

C++의 순열 시퀀스

예

입력

출력