C++ หาจำนวนการเรียงสับเปลี่ยนที่ไม่ซ้ำกันขึ้นต้นด้วย 1 ของสตริงไบนารี

ในปัญหานี้ เราได้รับสตริงที่ประกอบด้วย 0 และ 1 เราต้องหาจำนวนการเรียงสับเปลี่ยน (Permutations) ทั้งหมดที่สตริงขึ้นต้นด้วย 1 เนื่องจากคำตอบอาจใหญ่จึงพิมพ์ผลลัพธ์แบบ modulo 1,000,000,007

Input : str = "10101001001" Output : 210
Input : str = "101110011" Output : 56

เราจะแก้ปัญหานี้โดยใช้คณิตศาสตร์การจัดหมู่ (Combinatorics) และสร้างสูตรเพื่อคำนวณ

วิธีการแก้ปัญหา

นับจำนวน 0 และ 1 ในสตริง ให้ n = จำนวน 1, m = จำนวน 0, L = ความยาวสตริง สูตรคือ (L-1)! / ((n-1)! * m!)

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

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

long long fact(long long n) { 
    if(n <= 1) return 1; 
    return ((n % MOD) * (fact(n-1) % MOD)) % MOD; 
} 

int main() { 
    string s = "101110011"; 
    long long L = s.size(); 
    long long count_1 = 0, count_0 = 0; 
    for(auto x : s) { 
        if(x == '1') count_1++; 
        else count_0++; 
    } 
    if(count_1 == 0){ 
        cout << "0\n"; 
    } else { 
        long long factL = fact(L-1); 
        long long factn = fact(count_1 - 1); 
        long long factm = fact(count_0); 
        long long ans = factL / (factn * factm); 
        cout << ans << "\n"; 
    } 
    return 0; 
}

ผลลัพธ์

56

โปรแกรมนี้มีความซับซ้อนด้านเวลา O(N) โดย N คือความยาวสตริง

คำอธิบายโค้ด

เรานับจำนวน 1 และ 0 ในสตริง วาง 1 ตัวไว้หน้าสุด แล้วหาจำนวนการเรียงสับเปลี่ยนของ 0 และ 1 ที่เหลือในความยาว L-1 ซึ่งได้สูตร (L-1)! / ((n-1)! * m!) โดย (n-1)! คือการเรียงสับเปลี่ยนของ 1 ที่เหลือ และ m! คือการเรียงสับเปลี่ยนของ 0

สรุป

บทความนี้แก้ปัญหาการหาจำนวนการเรียงสับเปลี่ยนที่ไม่ซ้ำกันขึ้นต้นด้วย 1 ของสตริงไบนารี ด้วยคณิตศาสตร์การจัดหมู่และสูตรคำนวณ เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้เช่นกัน หวังว่าจะเป็นประโยชน์