การจัดเรียงที่สวยงามใน C++

สมมติว่าเรามีจำนวนเต็ม N จาก 1 ถึง N เราจะกำหนดการจัดเรียงที่สวยงามเป็นอาร์เรย์ที่สร้างโดยตัวเลข N เหล่านี้โดยสมบูรณ์ หากสิ่งใดสิ่งหนึ่งต่อไปนี้เป็นจริงสำหรับตำแหน่ง ith (1 <=i <=N) ในอาร์เรย์นี้ −

จำนวนที่ตำแหน่ง ith สามารถหารด้วย i.
i หารด้วยตัวเลขที่ตำแหน่ง ith ลงตัว

ดังนั้นหากอินพุตเป็น 2 ผลลัพธ์จะเป็น 2 เช่นกัน เนื่องจากการจัดเรียงที่สวยงามครั้งแรกคือ [1,2] โดยที่ตัวเลขในตำแหน่งที่ 1 (i=1) คือ 1 และ 1 หารด้วย i (i=1) ลงตัว จากนั้นจำนวนที่ตำแหน่งที่ 2 (i=2) คือ 2 และ 2 หารด้วย i (i=2) ลงตัว การจัดเรียงที่สวยงามอย่างที่สองคือ [2, 1]:ตัวเลขที่ตำแหน่งที่ 1 ในที่นี้ (i=1) คือ 2 และ 2 หารด้วย i ลงตัว (i=1) จากนั้นจำนวนที่ตำแหน่งที่ 2 (i=2) คือ 1 และ i (i=2) หารด้วย 1 ลงตัว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดวิธีการแบบเรียกซ้ำ (recursive method) ที่จะแก้ไข () ที่จะรับอาร์เรย์ที่เยี่ยมชม สิ้นสุด และ pos ตำแหน่งเริ่มต้นคือ 1.
ถ้า pos =end + 1 ให้เพิ่ม ans 1 แล้วกลับ
สำหรับฉันอยู่ในช่วง 1 ถึงสิ้นสุด
- ถ้าฉันไม่ถูกเยี่ยมชมและ pos หารด้วย 0 ลงตัว หรือ i หารด้วย 0 ลงตัวแล้ว
  - ทำเครื่องหมายว่าเยี่ยมชมแล้ว
  - แก้ไข(เยี่ยมชม, สิ้นสุด, pos + 1)
  - ทำเครื่องหมายว่าฉันไม่ได้เยี่ยมชม
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
ans :=0 สร้างอาร์เรย์ที่เรียกว่า visit
เรียกแก้ปัญหา(เยี่ยมชม, N, 1)r
ส่งคืน ans.

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int ans;
   void solve(vector <bool>& visited, int end, int pos = 1){
      if(pos == end + 1){
         ans++;
         return;
      }
      for(int i = 1; i <= end; i++){
         if(!visited[i] && (pos % i == 0 || i % pos == 0)){
            visited[i] = true;
            solve(visited, end, pos + 1);
            visited[i] = false;
         }
      }
   }
   int countArrangement(int N) {
      ans = 0;
      vector <bool> visited(N);
      solve(visited, N);
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.countArrangement(2));
}