จัดเรียงตัวเลข 1 ถึง N ใหม่ให้ห่างกัน K ใน C++

ภาพรวม

ได้รับจำนวนเต็ม N และ K งานคือคำนวณ Permutation ของ 1 ถึง N แล้วจัดเรียงใหม่ให้ทุกอิลิเมนต์ห่างจากตำแหน่งเดิม K หน่วย

ตัวอย่าง

อินพุต − n = 20, k = 2

เอาต์พุต − Rearrangement of first N numbers to make them at K distance is: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18

คำอธิบาย − Permutation ของ 20: 1..20 จัดเรียงใหม่ให้ทุกตัวห่างจากตำแหน่งเดิม 2 หน่วย

อินพุต − n = 10, k = 3

เอาต์พุต − Rearrangement of first N numbers to make them at K distance is: Not Possible

คำอธิบาย − ไม่สามารถจัดเรียงได้ด้วย N=10, K=3

แนวทางการแก้ปัญหา

• รับ N และ K
• เรียก Rearrangement(int n, int k)
• ภายในฟังก์ชัน:
  • temp = n % (2*k)
  • อาร์เรย์ ptr[n+1]
  • หาก k == 0 พิมพ์ 1 ถึง n คืนค่า
  • หาก temp != 0 พิมพ์ "Not Possible" คืนค่า
  • เติม ptr[i] = i สำหรับ i=1..n
  • วน i = 1; i <= n; i += 2*k:
    • วน j = 1; j <= k; j++ สลับ ptr[i+j-1] กับ ptr[k+i+j-1]
  • พิมพ์ ptr[1..n]
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

void Rearrangement(int n, int k){ 
    int temp = n % (2 * k); 
    int ptr[n + 1]; 
    if(k == 0){ 
        for(int i = 1; i <= n; i++){ 
            cout << i << " "; 
        } 
        return; 
    } 
    if(temp != 0){ 
        cout << "Not Possible"; 
        return; 
    } 
    for(int i = 1; i <= n; i++){ 
        ptr[i] = i; 
    } 
    for(int i = 1; i <= n; i += 2 * k){ 
        for(int j = 1; j <= k; j++){ 
            swap(ptr[i + j - 1], ptr[k + i + j - 1]); 
        } 
    } 
    for(int i = 1; i <= n; i++){ 
        cout << ptr[i] << " "; 
    } 
} 

int main(){ 
    int n = 20; 
    int k = 2; 
    cout << "Rearrangement of first N numbers to make them at K distance is: "; 
    Rearrangement(n, k); 
    return 0; 
}

ผลลัพธ์

Rearrangement of first N numbers to make them at K distance is: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18