หาจำนวน Permutation ที่มี K Inversions ด้วย C++

ในอาร์เรย์ คู่ a[i], a[j] เรียกว่า Inversion หาก a[i] > a[j] และ i < j เรามีตัวเลขสองตัว N และ k และต้องการหาว่ามี Permutation (การเรียงสับเปลี่ยน) ของตัวเลข N ตัวแรกกี่แบบที่มี Inversion อยู่ที่ K อย่างแน่นอน ตัวอย่าง:

Input: N = 4, K = 1 Output: 3 Explanation: Permutation ของ N ตัวแรกทั้งหมด: 1234, 1243, 1324, 2134. ที่มี 1 inversion คือ 1243, 1324, 2134
Input: N = 3, K = 2 Output: 3 Explanation: Permutation ทั้งหมด: 123, 132, 213, 231, 312, 321 ที่มี 2 inversions คือ 231, 312, 321

วิธีการหาคำตอบ

เราสามารถใช้ วิธี Brute Force ซึ่งคือ หา Permutation ทั้งหมดของ N ตัวแรก แล้วตรวจสอบ Inversion ทั้งหมดว่ามีค่าเท่ากับ K หรือไม่ หากใช่ ให้เพิ่มตัวนับผลลัพธ์

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เรามี N หลักของ N จำนวนธรรมชาติแรก Permutation ทั้งหมดของตัวเลขนั้นถูกคำนวณที่อื่นซึ่งเรากำลังมองหา K Permutation ในการหา เราจะนำตัวเลขถัดไป Nth (ตัวใหญ่สุด) ไปแทรกในทุก Permutation และมองหาตัวเลขที่จำนวน Inversion เท่ากับ K หลังจากเพิ่มตัวเลขนี้ ควรนับในผลลัพธ์ของเรา การนำ Permutation ของ (N-1) ตัวเลขที่ไม่มี (K-3) Inversion เราจะเลื่อนตัวเลขใหม่ไปที่ดัชนีที่ 3 จากท้าย จำนวน Inversion จะเป็น K และ find_permutations(N-1, K-3) จะเป็นคำตอบของเรา ตรรกะเดียวกันสามารถใช้ได้กับ Inversion อื่นๆ และเราจะได้ Recursion (ฟังก์ชันเรียกตัวเอง) ด้านบนเป็นคำตอบสุดท้าย

โค้ด

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

const int X = 100;
int a = 0;
int arr[X][X]; // ฟังก์ชัน Recursive

int find_permutations(int N_numbers, int K_inversion) {
    if (N_numbers == 0) {
        return 0; // คืนค่า 0 เมื่อ N กลายเป็น 0
    }
    if (K_inversion == 0)
        return 1; // คืนค่า 1 เมื่อ K กลายเป็น 1
    if (arr[N_numbers][K_inversion] != 0)
        return arr[N_numbers][K_inversion];
    
    int result = 0;
    for (int i = 0; i <= K_inversion; i++) {
        if (i <= N_numbers - 1)
            result += find_permutations(N_numbers - 1, K_inversion - i);
    }
    arr[N_numbers][K_inversion] = result;
    return result;
}

// ฟังก์ชันหลัก
int main() {
    int N, K;
    cin >> N; // รับอินพุตจากผู้ใช้
    cin >> K;
    cout << find_permutations(N, K);
    return 0;
}

ผลลัพธ์

0

Input - N = 4, K = 3

Output - 6

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวน Permutation ที่มี K Inversions จากความซับซ้อนด้านเวลา O(N × K) เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งแบบปกติและแบบมีประสิทธิภาพ สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน หวังว่าบทความนี้จะเป็นประโยชน์