Algoritma Kombinasi: Cetak semua Kemungkinan Kombinasi R

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 mana saja dan daftarkan semuanya. Misalnya, kami hanya memilih “RGBI” pada gambar 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.

Kode Pseudo

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 & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = 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 & lt; = end and end - i + 1 & gt; = 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

Kode Pseudo

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 & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = 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 & gt; = 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 tidak berurutan untuk melacak kombinasi duplikat

Jadi, jika kita tidak ingin mengurutkan elemen untuk melacak 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 & gt; = 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).

Dengan menggunakan metode sebelumnya untuk melacak duplikat, kita memerlukan O(n*log(n)) untuk menyortir; untuk membandingkan, kita memerlukan O(n), dan fungsi itu sendiri memerlukan O(n*n). Kompleksitas waktu total akan menjadi:

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

Apa Kombinasinya?

Analisis kompleksitas waktu untuk Kombinasi

Metode-1: Memperbaiki elemen dengan rekursi

Kode Pseudo

Implementasi di C/C++

Implementasi di Python

ARTIKEL TERKAIT

Metode 2 (Sertakan dan Kecualikan setiap elemen)

Kode Pseudo

Implementasi di C/C++

Implementasi di Python

Menangani Kombinasi Duplikat

Menggunakan kamus atau peta tidak berurutan untuk melacak kombinasi duplikat

Berikut implementasinya dengan python

Mendaftar untuk buletin