Algoritma Kombinasi: Cetak semua Kemungkinan Kombinasi R

⚡ Ringkasan Cerdas

Algoritma Kombinasi mencetak setiap kemungkinan pemilihan r item dari himpunan n, di mana urutan tidak penting. Sumber daya ini menjelaskan rumus kombinasi, kompleksitas waktu, dua metode rekursif, penanganan duplikat, dan kode C lengkap. C++, dan Python implementasi.

🎯 Definisi: Kombinasi memilih r item dari n item di mana urutan pemilihan tidak menjadi masalah.
🧮 Formula: Jumlah kombinasinya adalah nCr, sama dengan n! dibagi dengan r!(nr)!.
🔁 Metode 1: Rekursi elemen tetap memilih satu elemen, kemudian menemukan kombinasi dari r-1 elemen yang tersisa.
➕ Metode 2: Rekursi include-exclude berdasarkan identitas Pascal akan menggunakan atau melewatkan setiap elemen.
️ Duplikat: Pengurutan atau penggunaan kamus akan menghilangkan kombinasi yang berulang ketika input berisi nilai duplikat.

Baca Selengkapnya

Apa Kombinasinya?

Kombinasi adalah semacam susunan beberapa objek tertentu. Dalam istilah matematika, Kombinasi adalah sekumpulan pilihan/pemilihan item dari sekumpulan item/objek yang unik. Di sini, urutan item tidak menjadi masalah. Ini juga dikenal sebagai metode untuk menghitung hasil total suatu peristiwa, dimana urutan hasilnya tidak menjadi masalah.

Misalnya, Anda diberikan tas dengan 5 warna berbeda dan diminta membuat pola dengan 3 warna apa saja. Anda juga dapat memilih 3 warna dari 4 warna, lalu menyusunnya dalam urutan berbeda.

Misalkan warnanya adalah RGYBI(R= Merah, G= Hijau, Y= Kuning, B= Biru, I= Nila). Jadi, pola yang mungkin bisa berupa RGB, RGY, dll.

Mari kita lihat gambar berikut:

Penjelasan:

Ambil 4 warna dari 5 warna dan daftarkan
Dari setiap blok yang terdiri dari 4 warna, pilih 3 warna dan sebutkan semuanya. Misalnya, pada gambar kami hanya memilih “RGBI” dan menunjukkan 4 kombinasi.
Ada teori di baliknya untuk menghitung jumlah total kombinasi yang bisa kita buat. Kombinasi r elemen dari n dapat disajikan secara matematis sebagai:

Tanda "!" berarti faktorial. Sebagai contoh,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Katakan, 5! = 5*4*3*2*1 = 120

Jadi, untuk soal di atas, kita mempunyai 5 warna yang berarti n = 5, dan pada waktu tertentu, kita harus memilih 3 warna mana pun. Jadi, r = 3. Setelah menghitung, kita mendapatkan,

Sebanyak 10 kombinasi warna dimungkinkan untuk skenario di atas.

Analisis kompleksitas waktu untuk Kombinasi

Sekarang, katakanlah, sebuah array berukuran n, kita diminta untuk mengambil r elemen dari array dan melakukan kombinasi r elemen.

Jika array berukuran n diberikan, maka dibutuhkan O(n²) waktu untuk melakukan tugas. Juga, jika kita ingin menghapus entri duplikat, maka,

Kita perlu melakukan langkah-langkah berikut:

Langkah 1) Urutkan data array input secara ascending. Kompleksitas Waktu pengurutan adalah HAI(n*log(n)).

Langkah 2) Buat array lain yang berisi elemen unik dari data array sementara yang diberikan.

Langkah 3) Kemudian, lakukan fungsi kombinasi.

Jadi, total kompleksitas waktu menjadi = Di²) + O(nLog(n)). Kita dapat menganggapnya O(n²), sebagai n²jauh lebih besar dari n*log(n).

Metode-1: Memperbaiki elemen dengan rekursi

Dalam metode ini, kita akan memilih sebuah elemen lalu mencari kombinasi r-1 elemen. Saat kita mengambil sebuah elemen dari elemen lainnya, kita melakukannya secara rekursif, dan itulah mengapa ini disebut elemen tetap dan rekursi.

Mari kita tunjukkan algoritme langkah demi langkah dengan diagram:

Langkah-langkah diberikan di bawah ini:

Langkah 1) Pada lapisan pertama, ambil elemen n-r+1. Artinya kita mengambil 3 elemen.

Langkah 2) Pilih elemen dari lapisan ke-2 dan bawa ke nr. Jadi, jika kita mengambil “R”, maka dengan R, kita dapat mengambil G, Y, dan B.

Langkah 3) Pilih elemen dari lapisan ke-3 dan bawa ke elemen ke-n, dan bentuk blok yang masing-masing berisi 3 elemen.

Gambar di atas adalah nilai kembalian dari rekursi. Hanya lapisan terakhir yang akan dicetak.

Pseudo Code

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

Implementasi di C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i < r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

Keluaran:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Implementasi di Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i <= end and end - i + 1 >= r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

Keluaran:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Metode 2 (Sertakan dan Kecualikan setiap elemen)

Metode ini didasarkan pada identitas Pascal. Sebelumnya, kita menggunakan rekursi untuk menghitung nCr. Di sini, metode ini hanya dibagi, bukan loop kompleks.

Menurut identitas Pascal,

nCr = (n-1)Cr + (n-1)C(r-1)

Jadi, akan ada 2 logika rekursif untuk algoritma rekursif untuk menemukan Kombinasi r elemen dari array berukuran n tertentu.

Elemen disertakan dalam Kombinasi saat ini
Elemen dikecualikan dari Kombinasi saat ini

Pseudo Code

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

Implementasi di C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j < r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i >= n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

Keluaran:

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Implementasi di Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i >= n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

Keluaran:

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Menangani Kombinasi Duplikat

Terkadang mungkin ada elemen duplikat dalam array masukan.

Sebagai contoh,

Array masukan berisi n = {5, 2, 3, 1, 5}.
Di sini kita dapat melihat bahwa 5 hadir sebanyak 2 kali.
Sekarang, jika kita ingin menjalankan kode untuk array ini, beberapa kombinasi akan diulang.
Kita akan menemukan {5, 2, 5}, {5, 2, 3} dst atau kombinasi apa pun yang mengandung 5, akan diulang.

Kita dapat menggunakan dua metode ini:

Urutkan array masukan. Penyortiran akan memakan waktu O(nlog(n)).
Kemudian tingkatkan nilai i, sementara nilai i dan nilai i+1 sama. Pada dasarnya masukkan dua baris kode berikut ke dalam fungsi Combination.

// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

Menggunakan kamus atau peta tak terurut untuk track kombinasi duplikat

Jadi, jika kita tidak ingin mengurutkan elemen untuk tracUntuk mendapatkan duplikatnya, kita dapat mengikuti langkah-langkah yang diberikan.

Langkah 1) Deklarasikan kamus global atau peta hash.
Langkah 2) Dorong Kombinasi yang dihasilkan ke peta hash dan tingkatkan nilainya satu per satu. Kombinasinya adalah kuncinya, dan kemunculannya adalah nilai.
Langkah 3) ketika fungsi selesai berjalan, kita cukup mencetak semua kunci dari hashmap atau kamus.

Berikut implementasinya dengan python

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i >= n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

Keluaran:

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

Di sini, Anda dapat melihat bahwa masukannya adalah “RGYBIB.” Umumnya, akan terjadi beberapa kombinasi duplikat. Namun karena kami menggunakan kamus dan memperlakukan setiap Kombinasi sebagai kuncinya, kami hanya dapat mencetak Kombinasi unik.

Sekarang, jika Anda menulis “print(unique_combination)”, Anda dapat melihat frekuensi setiap kombinasi. Ini akan ditampilkan seperti ini:

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

Jadi, kita dapat melihat bahwa RGB, RYB, GYB telah terjadi 2 kali. Kompleksitas waktu untuk memasukkan kunci ke dalam kamus pada dasarnya adalah O(1). Jadi, jika Anda menggunakan kamus, maka total kompleksitas waktu untuk menjalankan kode tersebut adalah:

HAI(1) + HAI(n*n)

Setara dengan O(n*n).

Menggunakan metode sebelumnya untuk tracJika terdapat k duplikat, kita membutuhkan O(n*log(n)) untuk pengurutan; untuk perbandingan, kita membutuhkan O(n), dan fungsi itu sendiri membutuhkan O(n*n). Kompleksitas waktu total akan menjadi:

HAI(n*log(n)) + O(n) +O(n*n)

Pertanyaan Umum Demo Slot

Kombinasi adalah pemilihan di mana urutan tidak penting, sehingga RGB dan BGR dihitung sebagai satu. Permutasi adalah susunan di mana urutan penting, sehingga RGB dan BGR dihitung sebagai dua. Kombinasi menggunakan nCr; permutasi menggunakan nPr.

nCr adalah jumlah cara untuk memilih r item dari n item ketika urutan tidak penting. Perhitungannya adalah n! dibagi r! dikalikan (nr)!. Misalnya, 5C3 sama dengan 10.

Algoritma kombinasi muncul dalam peluang lotere, pemilihan tim atau komite, pencarian subset fitur dalam pembelajaran mesin, pembuatan kasus uji, dan analisis kata sandi atau ruang kunci. Di mana pun Anda memilih sebuah grup tanpa memperhatikan urutan, kombinasi berlaku.

Alat AI dapat menghasilkan semua kombinasi dari sebuah dataset, menyaring duplikat, dan bahkan menyarankan metode yang paling efisien untuk input yang besar. Ini menghemat waktu, meskipun Anda harus memverifikasi jumlahnya terhadap rumus nCr untuk memastikan kebenarannya.

Ya. Asisten pengkodean AI dapat menulis kode kombinasi dalam bahasa C, C++, Python, dan bahasa lainnya, termasuk metode rekursif dan include-exclude. Selalu uji output dan periksa kasus-kasus khusus seperti elemen duplikat atau r lebih besar dari n.

Algoritma Kombinasi: Cetak semua Kemungkinan Kombinasi R

Apa Kombinasinya?

Analisis kompleksitas waktu untuk Kombinasi

Metode-1: Memperbaiki elemen dengan rekursi

Pseudo Code

Implementasi di C/C++

Implementasi di Python

Metode 2 (Sertakan dan Kecualikan setiap elemen)

Pseudo Code

Implementasi di C/C++

Implementasi di Python

Menangani Kombinasi Duplikat

Menggunakan kamus atau peta tak terurut untuk track kombinasi duplikat

Berikut implementasinya dengan python

Pertanyaan Umum Demo Slot

Ringkaslah postingan ini dengan:

Mendaftar untuk buletin