ลำดับการเรียงสับเปลี่ยนใน C++

สมมติว่าชุดนั้นเหมือน [1,2,3,...,n] มีทั้งหมด n! พีชคณิตที่ไม่ซ้ำกัน โดยการแสดงรายการและติดป้ายกำกับการเรียงสับเปลี่ยนทั้งหมดตามลำดับ เราได้ลำดับเหล่านี้สำหรับ n =3:["123","132","213","231","312","321"] ดังนั้นถ้า n และ k จะได้รับ จากนั้นส่งคืนลำดับการเรียงสับเปลี่ยน kth n จะอยู่ระหว่าง 1 ถึง 9 (รวม) และ k จะอยู่ระหว่าง 1 ถึง n! (รวม) ตัวอย่างเช่น ถ้า n =3

ให้เราดูขั้นตอน -

• ans :=สตริงว่าง กำหนดอาร์เรย์ที่เรียกว่าตัวเลือกที่มีขนาด n
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ผู้สมัคร[i] :=((i + 1) + ตัวอักษร '0')
• สร้างหนึ่งอาร์เรย์ที่เรียกว่า fact of size n + 1, set fact[0] :=1
• สำหรับฉันอยู่ในช่วง 1 ถึง n
  • fact[i] :=fact[i – 1] * i
• ลด k ขึ้น 1
• สำหรับ i :=n – 1 เหลือ 0
  • idx :=k / ข้อเท็จจริง[i]
  • ans :=ans + ผู้สมัคร[idx]
  • สำหรับ j :=idx, j + 1 <ขนาดของผู้สมัคร
    • ผู้สมัคร[j] :=ผู้สมัคร[j + 1]
  • k :=k mod ข้อเท็จจริง[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

ผลลัพธ์

2314