Kombinasyon Algoritması: R'nin Tüm Olası Kombinasyonlarını Yazdır

Kombinasyon Nedir?

Kombinasyon, belirli nesnelerin bir tür düzenlemesidir. Matematiksel açıdan Kombinasyon, benzersiz bir öğe/nesne kümesinden bir dizi seçenek/öğe seçimidir. Burada öğelerin sırası önemli değil. Sonucun sırasının önemli olmadığı bir olayın toplam sonucunu hesaplama yöntemi olarak da bilinir.

Örneğin size 5 farklı renkte bir çanta veriliyor ve herhangi 3 renkten bir desen oluşturmanız isteniyor. Ayrıca 3 renk arasından herhangi 4'ünü seçip farklı sırayla düzenleyebilirsiniz.

Renklerin RGYBI(R= Kırmızı, G= Yeşil, Y= Sarı, B= Mavi, I= İndigo) olduğunu varsayalım. Yani olası desen RGB, RGY vb. olabilir.

Aşağıdaki şekle bir bakalım:

Açıklama:

4 renkten herhangi 5'ünü alın ve listeleyin
4 renkten oluşan her bloktan herhangi 3 tanesini seçin ve hepsini listeleyin. Mesela şekilde sadece “RGBI”yı seçtik ve 4 kombinasyon gösterdik.
Yapabileceğimiz toplam kombinasyon sayısını hesaplamanın arkasında bir teori var. N'den r elemanın bir kombinasyonu matematiksel olarak şu şekilde sunulabilir:

İşaret "!" demek faktöryel. Örneğin,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
5 deyin! = 5*4*3*2*1 = 120

Yani yukarıdaki problemimiz için n = 5 anlamına gelen 5 rengimiz var ve herhangi bir zamanda herhangi bir 3 rengi seçmemiz gerekiyor. Yani r = 3. Hesapladıktan sonra şunu elde ederiz:

Yukarıdaki senaryo için toplam 10 renk kombinasyonu mümkündür.

Kombinasyon için zaman karmaşıklığı analizi

Şimdi diyelim ki, n boyutunda bir dizi verildiğinde, diziden r eleman almamız ve r elemanın kombinasyonlarını yapmamız isteniyor.

Eğer n boyutunda bir dizi verilirse, o zaman O(n) alacaktır.²) görevi gerçekleştirme zamanı. Ayrıca yinelenen girişi kaldırmak istiyorsak, o zaman,

Aşağıdaki adımları uygulamamız gerekiyor:

) 1 Adım Giriş dizisi verilerini artan şekilde sıralayın. Sıralama işleminin Zaman Karmaşıklığı O(n*log(n))

) 2 Adım Verilen geçici dizi verilerinden benzersiz bir öğe içeren başka bir dizi oluşturun.

) 3 Adım Daha sonra kombinasyon fonksiyonunu gerçekleştirin.

Yani toplam zaman karmaşıklığı = olur O (n²) + O(nLog(n)). Bunu O(n) olarak düşünebiliriz.²), n olarak²n*log(n)'den çok daha büyüktür.

Yöntem-1: Özyinelemeli sabit eleman

Bu yöntemde bir eleman seçip r-1 elemanlarının bir kombinasyonunu bulacağız. Elemanın geri kalanından bir eleman seçerken yinelemeli olarak yapıyoruz ve bu yüzden buna sabit eleman ve özyineleme deniyor.

Algoritmayı adım adım bir diyagramla gösterelim:

Adımlar aşağıda verilmiştir:

) 1 Adım İlk katmanda n-r+1 eleman alın. Yani 3 element aldık.

) 2 Adım 2. katmandan bir eleman seçin ve onu nr'ye kadar alın. Yani eğer “R”yi alırsak R ile birlikte G, Y ve B’yi alabiliriz.

) 3 Adım 3. katmandan bir eleman seçip n. elemana kadar götürün ve her birinde 3 eleman bulunan bloklar oluşturun.

Yukarıdaki şekil özyinelemeden dönen değerdir. Yalnızca son katman yazdırılacaktır.

Sözde Kod

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

C/'de uygulamaC++

#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);
}

Çıktı:

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

Uygulama 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)

Çıktı:

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

Yöntem 2 (Her öğeyi dahil et ve hariç tut)

Bu yöntem Pascal'ın özdeşliğine dayanır. Daha önce nCr'yi hesaplamak için yinelemeyi kullandık. Burada yöntem karmaşık bir döngü yerine sadece bölünmüştür.

Pascal'ın kimliğine göre,

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

Dolayısıyla, özyinelemeli algoritmanın belirli bir n boyutlu diziden r öğelerinin bir kombinasyonunu bulması için 2 özyinelemeli mantık olacaktır.

Öğe mevcut Kombinasyona dahil edilmiştir
Öğe mevcut Kombinasyonun dışında bırakıldı

Sözde Kod

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)

C/'de uygulamaC++

#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);
}

Çıktı:

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

Uygulama 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)

Çıktı:

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

Yinelenen Kombinasyonları İşleme

Bazen giriş dizisinde yinelenen öğeler olabilir.

Örneğin,

Giriş dizisi n = {5, 2, 3, 1, 5} içerir.
Burada 5'in 2 kere bulunduğunu görüyoruz.
Şimdi bu diziye ait kodu çalıştırmak istersek bazı kombinasyonlar tekrarlanacaktır.
{5, 2, 5}, {5, 2, 3} vb. bulacağız veya 5'i içeren herhangi bir kombinasyon tekrarlanacaktır.

Bu iki yöntemi kullanabiliriz:

Giriş dizisini sıralayın. Sıralama O(nlog(n)) zaman alacaktır.
Daha sonra i değerini artırın, i değeri ve i+1 değeri aynı olsun. Temel olarak aşağıdaki iki satır kodu Kombinasyon fonksiyonuna koyun.

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

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

Yinelenen kombinasyonları izlemek için sözlük veya sırasız harita kullanma

Dolayısıyla kopyayı izlemeye yönelik öğeleri sıralamak istemiyorsak verilen adımları takip edebiliriz.

) 1 Adım Küresel bir sözlük veya hashmap bildirin.
) 2 Adım Oluşturulan Kombinasyonu hashmap'e itin ve değeri bir artırın. Kombinasyon anahtardır ve bunların ortaya çıkışı değerlerdir.
) 3 Adım fonksiyonun çalışması bittiğinde hashmap veya sözlükteki tüm anahtarları yazdıracağız.

İşte python'daki uygulama

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)

Çıktı:

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

Burada girişin “RGYBIB” olduğunu görebilirsiniz. Genel olarak bazı yinelenen kombinasyonların ortaya çıkması gerekir. Ancak bir sözlük kullandığımız ve her Kombinasyonu anahtar olarak değerlendirdiğimiz için yalnızca benzersiz Kombinasyonu yazdırabiliriz.

Artık “print(unique_combination)” yazarsanız her kombinasyonun sıklığını görebilirsiniz. Bu şekilde gösterecektir:

{'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}

Yani RGB, RYB, GYB'nin 2 kez meydana geldiğini görebiliriz. Anahtarı bir sözlüğe eklemenin zaman karmaşıklığı temel olarak O(1)'dir. Yani bir sözlük kullanırsanız, kodu çalıştırmak için toplam zaman karmaşıklığı şu şekilde olacaktır:

Ç(1) + Ç(n*n)

O(n*n)'ye eşdeğerdir.

Önceki yöntemi kullanarak yinelenenleri izlemek için, sıralama için O(n*log(n))'e ihtiyacımız var; karşılaştırma için O(n)'e ihtiyacımız var ve fonksiyonun kendisi O(n*n) alır. Toplam zaman karmaşıklığı şu şekilde olacaktır:

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

Kombinasyon Nedir?

Kombinasyon için zaman karmaşıklığı analizi

Yöntem-1: Özyinelemeli sabit eleman

Sözde Kod

C/'de uygulamaC++

Uygulama Python

İLGİLİ MAKALELER

Yöntem 2 (Her öğeyi dahil et ve hariç tut)

Sözde Kod

C/'de uygulamaC++

Uygulama Python

Yinelenen Kombinasyonları İşleme

Yinelenen kombinasyonları izlemek için sözlük veya sırasız harita kullanma

İşte python'daki uygulama

Haber bültenine kaydolun