Stars and bars: distribuții și combinatorică în C++

Metoda stars and bars numără distribuțiile unor obiecte identice în cutii distincte. Ea transformă o problemă despre sume de numere naturale într-o alegere de poziții pentru separatoare. Formula este utilă numai după ce verifici exact ce este distinct și dacă sunt permise cutii goale.

Pentru n obiecte identice și k cutii distincte, cu n >= 0 și k >= 1, numărul distribuțiilor este C(n+k-1,k-1). Echivalent, numărăm soluțiile întregi nenegative ale ecuației x1+...+xk=n.

Cum funcționează

Scriem n steluțe într-un șir și introducem k-1 bare. Numărul steluțelor dinaintea primei bare este x1, dintre primele două bare este x2 și așa mai departe. Barele alăturate reprezintă cutii goale. O bară la început sau la sfârșit înseamnă că prima sau ultima cutie este goală.

Avem n+k-1 poziții totale și alegem k-1 dintre ele pentru bare. Restul sunt steluțe, deci nu mai există o alegere suplimentară. Cutia este identificată prin poziția grupului, nu printr-o etichetă adăugată fiecărui obiect. Dacă obiectele ar fi distincte, această codificare ar pierde informație și formula nu s-ar mai aplica.

Dacă toate cutiile trebuie să fie nevide, punem mai întâi câte un obiect în fiecare. Rămân n-k obiecte de distribuit liber; pentru n>=k obținem C(n-1,k-1). Dacă n<k, răspunsul este zero. Pentru limite inferioare diferite, scădem din n suma minimelor și transformăm fiecare variabilă prin yi=xi-minim_i.

Limitele superioare schimbă problema: distribuirea liberă poate produce cutii prea pline. Atunci avem nevoie de o corecție prin includere-excludere sau de programare dinamică, în funcție de limite. Programul de aici tratează numai varianta fără limite superioare, cu n+k-1 <= 30. Formula multiplicativă pentru combinații evită factorialele mari și păstrează rezultate exacte în long long pentru această limită.

Exemplu urmărit pas cu pas

Pentru trei obiecte și două cutii, șirurile sunt |*, *|, *| și ***|. Ele corespund distribuțiilor (0,3), (1,2), (2,1), (3,0). Avem C(4,1)=4 posibilități.

Dacă ambele cutii trebuie să fie nevide, rămân doar (1,2) și (2,1). Formula devine C(2,1)=2. Pentru zero obiecte și trei cutii există exact o distribuție, toate goale; reprezentarea conține doar două bare.

Implementare C++17

#include <iostream>
long long choose(int n, int k) {
    if (k > n - k)
        k = n - k;
    long long result = 1;
    for (int i = 1; i <= k; ++i)
        result = result * (n - k + i) / i;
    return result;
}
int main() {
    int n, k;
    std::cin >> n >> k;
    std::cout << choose(n + k - 1, k - 1) << '\n';
}

De ce funcționează și cât costă

Codificarea este bijectivă: fiecare distribuție produce un singur șir de steluțe și bare, iar fiecare șir determină o singură distribuție. Numărarea pozițiilor barelor numără astfel exact soluțiile, fără omisiuni și fără dubluri.

Calculul unei combinații folosește O(min(k,n-k)) pași pentru argumentele funcției choose și O(1) memorie. Enumerarea tuturor distribuțiilor prin backtracking are în schimb un cost cel puțin proporțional cu numărul rezultatelor; numărarea și enumerarea sunt cerințe diferite.

Greșeli frecvente

Nu aplica formula dacă obiectele sunt distincte sau cutiile nedistincte. Nu confunda natural nenegativ cu strict pozitiv. Nu calcula factoriale în int doar pentru că argumentele sunt mici. Înmulțirea intermediară trebuie și ea să încapă în tip.

Exersează

Câte soluții nenegative are x+y+z=4? Câte sunt strict pozitive?

Rezolvare explicată: Fără restricții de pozitivitate avem C(6,2)=15. Pentru soluții strict pozitive scădem câte unu din fiecare variabilă și rămâne suma 1: C(3,2)=3.

Continuă să înveți

Combinări, backtracking și programare dinamică.

Întrebări frecvente

De ce sunt doar k-1 separatoare?

Separatoarele împart șirul în k grupuri: înaintea primei bare, între bare și după ultima. Nu este necesară o bară după fiecare grup.

Ce înseamnă două bare consecutive?

Cutia dintre ele conține zero obiecte. Acesta este motivul pentru care metoda standard admite variabile nenegative.

Cum impun ca fiecare cutie să fie nevidă?

Rezervă câte un obiect pentru fiecare cutie și distribuie restul. Dacă nu există suficiente obiecte, numărul soluțiilor este zero.

Pot impune cel mult două obiecte în fiecare cutie?

Formula simplă nu mai este suficientă. Trebuie excluse distribuțiile care depășesc limita sau folosită o stare dinamică ce o respectă explicit.

Este aceeași problemă dacă obiectele sunt distincte?

Nu. Atunci contează ce obiect ajunge în fiecare cutie, nu doar câte. Codificarea prin steluțe identice nu păstrează această informație.