Permutation dan Combination

Banyak soal kombinatorial berakhir pada dua pertanyaan klasik: berapa banyak susunan berurutan yang mungkin, dan berapa banyak himpunan bagian berukuran k. Permutation menjawab pertanyaan pertama — urutan memedulikan posisi, sehingga [1, 2, 3] dan [2, 1, 3] dihitung dua permutasi berbeda. Combination menjawab pertanyaan kedua — urutan diabaikan, sehingga {1, 2} dan {2, 1} dihitung satu kombinasi yang sama. Pada Chapter ini kita akan membangkitkan semua permutation dari sebuah array dengan rekursi berbasis swap, memakai std::next_permutation sebagai alternatif STL, lalu membangkitkan semua combination dengan pola include/exclude klasik backtracking.

Aturan: Permutation vs Combination #

Misalkan tersedia n elemen dan kita memilih k di antaranya.

Konsep	Rumus	Urutan?	Contoh untuk `{1,2,3}` dengan `k=2`
Permutation P(n, k)	`n! / (n-k)!`	Ya, peduli	(1,2), (1,3), (2,1), (2,3), (3,1), (3,2) — 6 buah
Combination C(n, k)	`n! / (k!·(n-k)!)`	Tidak peduli	{1,2}, {1,3}, {2,3} — 3 buah

Perbedaan kuncinya: permutation memperlakukan posisi (slot), combination memperlakukan keanggotaan (isi). Itulah sebabnya P(n, k) selalu ≥ C(n, k); setiap kombinasi berukuran k menyetorkan tepat k! permutasi.

Permutation: Swap-Based Recursion #

Aturan #

Untuk membangkitkan semua permutasi dari n elemen, kita menempatkan elemen satu per satu ke slot 0, 1, …, n-1. Pada slot i, kita mencoba setiap elemen yang belum dipakai dengan menukarnya ke posisi i, lalu rekursi ke slot i+1. Setelah rekursi selesai, kita menukar kembali agar state pulih — pola choose-explore-unchoose klasik.

Mekanisme Kerja #

Vektor a berperan ganda: sebagai kumpulan elemen dan sebagai penanda slot yang sudah terisi (bagian [0, i) sudah fixed, bagian [i, n) masih bebas ditukar). Pada setiap level rekursif i, kita mencoba menukar a[i] dengan a[j] untuk semua j ≥ i. Setelah swap, a[i] berisi kandidat final untuk slot i, dan sisa [i+1, n) tetap bebas. Swap balik setelah rekursi memastikan tidak ada polusi state ke cabang saudara.

Pohon rekursi untuk a = {1, 2, 3} terlihat seperti berikut:

flowchart TD Root["[1,2,3] slot i=0"] --> S00["swap(0,0) → [1,2,3]"] Root --> S01["swap(0,1) → [2,1,3]"] Root --> S02["swap(0,2) → [3,2,1]"] S00 --> L1["[1,2,3] i=1"] L1 --> T11["swap(1,1) → [1,2,3] → output"] L1 --> T12["swap(1,2) → [1,3,2] → output"] S01 --> L2["[2,1,3] i=1"] L2 --> T21["swap(1,1) → [2,1,3] → output"] L2 --> T22["swap(1,2) → [2,3,1] → output"] S02 --> L3["[3,2,1] i=1"] L3 --> T31["swap(1,1) → [3,2,1] → output"] L3 --> T32["swap(1,2) → [3,1,2] → output"]

Setiap jalur dari root ke daun menghasilkan satu permutasi. Banyaknya daun = n! karena pada level i ada tepat n-i pilihan swap.

Kode: Generator Permutasi Rekursif #

cpp
#include <iostream>
#include <vector>

void permutasi(std::vector<int>& a, size_t i) {
    if (i == a.size()) {                       // semua slot terisi
        for (int x : a) std::cout << x << ' ';
        std::cout << '\n';
        return;
    }
    for (size_t j = i; j < a.size(); ++j) {
        std::swap(a[i], a[j]);                 // choose
        permutasi(a, i + 1);                   // explore
        std::swap(a[i], a[j]);                 // unchoose
    }
}

int main() {
    std::vector<int> a = {1, 2, 3};
    std::cout << "permutasi dari {1,2,3}:\n";
    permutasi(a, 0);
    return 0;
}

Output yang Dihasilkan:

text
permutasi dari {1,2,3}:
2 3 
3 2 
1 3 
3 1 
2 1 
1 2 

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

Parameter i: indeks slot yang sedang diisi. Base case tercapai saat i == a.size(), artinya semua slot 0..n-1 sudah berisi elemen final.
Loop for (size_t j = i; j < a.size(); ++j): iterasi kandidat swap. Karena slot [0, i) sudah fixed, kandidat hanya berasal dari [i, n).
Baris std::swap(a[i], a[j]) (choose): pindahkan elemen dari posisi j ke slot i. Sekarang a[i] final untuk cabang ini.
Baris permutasi(a, i + 1) (explore): rekursi untuk mengisi slot berikutnya dengan sisa array [i+1, n).
Baris std::swap(a[i], a[j]) (unchoose): pulihkan urutan semula agar cabang saudara (iterasi j berikutnya) mulai dari state yang sama. Tanpa swap balik ini, output akan rusak karena elemen tertinggal di slot yang salah.
Total 6 output: untuk n = 3, banyak permutasi = 3! = 6.

Alternatif STL: std::next_permutation #

STL C++ menyediakan std::next_permutation yang membangkitkan permutasi berikutnya dalam urutan leksikografis. Syaratnya: container harus sudah terurut menaik sebelum loop dimulai. Setiap pemanggilan mengembalikan true bila permutasi berikutnya ada (lebih besar secara leksikografis), dan false bila sudah kembali ke permutasi terkecil (yang artinya semua sudah dijelajahi).

Kode: std::next_permutation #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> a = {1, 2, 3};
    std::cout << "permutasi dengan std::next_permutation:\n";
    do {
        for (int x : a) std::cout << x << ' ';
        std::cout << '\n';
    } while (std::next_permutation(a.begin(), a.end()));
    return 0;
}

Output yang Dihasilkan:

text
permutasi dengan std::next_permutation:
2 3 
3 2 
1 3 
3 1 
1 2 
2 1 

Perbedaan utama dibanding versi swap-based:

Urutan leksikografis: output terurut naik dari 1 2 3 hingga 3 2 1. Versi swap-based tidak menjamin urutan ini.
Perlu data terurut: bila a tidak di-sort lebih dulu, std::next_permutation hanya membangkitkan permutasi yang ≥ konfigurasi awal, bukan semua n! permutasi.
In-place: algoritma memodifikasi langsung tanpa alokasi tambahan. Kompleksitas per pemanggilan O(n).

Combination: Pola Include/Exclude #

Aturan #

Kombinasi C(n, k) berarti memilih tepat k elemen dari n, tanpa mempedulikan urutan. Strategi klasik: untuk setiap elemen (diproses dari indeks 0 ke n-1), kita putuskan include (masukkan ke himpunan hasil) atau exclude (lewati). Setiap cabang rekursi mempersempit elemen yang tersisa dan jumlah slot yang masih dibutuhkan.

Mekanisme Kerja #

Kita menyimpan indeks start (indeks elemen berikutnya yang akan dipertimbangkan) dan cur (vektor penampung kombinasi yang sedang dibangun). Base case: bila cur.size() == k, catat. Untuk menghindari duplikasi akibat urutan, kita hanya memilih elemen dengan indeks ≥ start — yaitu kita memproses elemen secara monotonic naik. Hasilnya, himpunan {1, 3} hanya dibangkitkan satu kali (lewat jalur 1→3), tidak pernah 3→1.

Kode: Generator Kombinasi Rekursif #

cpp
#include <iostream>
#include <vector>

void kombinasi(const std::vector<int>& a, size_t start, size_t k,
               std::vector<int>& cur)
{
    if (cur.size() == k) {                     // terpilih tepat k elemen
        for (int x : cur) std::cout << x << ' ';
        std::cout << '\n';
        return;
    }
    for (size_t i = start; i < a.size(); ++i) {
        cur.push_back(a[i]);                   // choose: include a[i]
        kombinasi(a, i + 1, k, cur);            // explore: lanjut ke i+1
        cur.pop_back();                         // unchoose: exclude a[i]
    }
}

int main() {
    std::vector<int> a = {1, 2, 3, 4};
    size_t k = 2;
    std::vector<int> cur;
    std::cout << "kombinasi C(4,2):\n";
    kombinasi(a, 0, k, cur);
    return 0;
}

Output yang Dihasilkan:

text
kombinasi C(4,2):
2 
3 
4 
3 
4 
4 

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

Parameter start: indeks minimum yang boleh dipilih. Memulai dari 0 di panggilan akar, dan dinaikkan menjadi i + 1 setelah memilih a[i]. Ini memastikan urutan indeks yang dipilih selalu naik, sehingga {1, 3} dan {3, 1} tidak dihitung dua kali.
Parameter cur: vektor penampung kombinasi parsial. Di-pass by reference agar push_back dan pop_back langsung terlihat di seluruh kedalaman rekursi.
Base case cur.size() == k: cukup elemen terkumpul. Cetak dan kembali tanpa melanjutkan loop.
Baris cur.push_back(a[i]) (choose): sertakan a[i] sebagai elemen ke-|cur|+1 dalam kombinasi.
Baris kombasi(a, i + 1, k, cur) (explore): rekursi dengan start = i + 1 agar elemen berikutnya harus berasal dari indeks setelah i. Tanpa kenaikan ini, kombinasi akan mengulang elemen yang sama dan menghasilkan [1, 1], [1, 2], dst — bukan kombinasi melainkan penyusunan dengan pengulangan.
Baris cur.pop_back() (unchoose): keluarkan a[i] dari cur agar cabang berikutnya (yang mengeksklusi a[i]) mulai dari state bersih.
Total 6 output: untuk n=4, k=2, C(4, 2) = 6. Konsisten dengan rumus.

Perbandingan Pendekatan #

Aspek	Permutation (swap)	Permutation (STL)	Combination (include/exclude)
Jumlah hasil	`n!`	`n!`	`C(n, k) = n! / (k!(n-k)!)`
Urutan output	DFS arbitrary	Leksikografis	Leksikografis (bila input sorted)
Perlu input sorted?	Tidak	Ya	Tidak (urutan mengikuti input)
Duplikat otomatis skip?	Tidak	Ya (multiset aman)	Tidak
Kompleksitas waktu	O(n · n!)	O(n · n!)	O(k · C(n, k))

Ringkasan #

Permutation mempedulikan urutan; combination tidak. P(n, k) = n!/(n-k)!, C(n, k) = n!/(k!(n-k)!).
Generator permutasi swap-based memakai pola choose-explore-unchoose dengan swap(a[i], a[j]) lalu swap balik.
std::next_permutation adalah alternatif STL: in-place, leksikografis, dan otomatis melewati duplikat — namun wajib memulai dari container terurut.
Generator kombinasi memakai loop dengan start monoton naik, sehingga himpunan tidak terbangkitkan dua kali akibat permutasi internal.
Kompleksitas waktu ketiganya proporsional terhadap jumlah hasil dikali panjang output, yaitu O(n · n!) untuk permutasi dan O(k · C(n, k)) untuk kombinasi.