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

⚡ Akıllı Özet

Kombinasyon algoritması, n öğeden oluşan bir kümeden r öğenin olası tüm seçimlerini yazdırır; burada sıralama önemli değildir. Bu kaynak, kombinasyon formülünü, zaman karmaşıklığını, iki özyinelemeli yöntemi, yinelenen öğelerin işlenmesini ve eksiksiz C kodunu açıklamaktadır. C++, ve Python uygulamalar.

🎯 Tanım: Bir kombinasyon, seçim sırasının önemli olmadığı n öğeden r öğeyi seçme işlemidir.
🧮 formül: Kombinasyon sayısı nCr'dir ve n!'in r!'e (nr)!) bölünmesine eşittir.
🔁 Yöntem 1: Sabit elemanlı özyineleme, bir eleman seçer ve ardından kalan r-1 elemanın kombinasyonlarını bulur.
➕ Yöntem 2: Pascal özdeşliğine dayalı bir dahil etme-hariç tutma özyinelemesi, her öğeyi ya kullanır ya da atlar.
🗂️ çoğaltmaları: Sıralama veya sözlük, girişte yinelenen değerler olduğunda tekrarlanan kombinasyonları ortadan kaldırır.

Devamını Oku

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
Her 4 renk bloğundan herhangi 3 tanesini seçin ve hepsini listeleyin. Örneğin, şekilde sadece "RGBI" renklerini 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 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

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

Çı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 <= 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)

Çı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 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)

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

Çı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 >= 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

Sözlük veya sıralı olmayan harita kullanarak track tekrarlanan kombinasyonlar

Yani, eğer öğeleri sıralamak istemiyorsak... tracKopyayı oluşturmak için 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 >= 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 track adet kopya varsa, sıralama için O(n*log(n)); karşılaştırma için O(n) gerekir ve fonksiyonun kendisi O(n*n) sürer. Toplam zaman karmaşıklığı şu olacaktır:

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

SSS

Kombinasyon, sıranın önemli olmadığı bir seçimdir; bu nedenle RGB ve BGR bir olarak sayılır. Permütasyon ise sıranın önemli olduğu bir düzenlemedir; bu nedenle RGB ve BGR iki olarak sayılır. Kombinasyonlar nCr, permütasyonlar ise nPr kullanır.

nCr, sıralamanın önemli olmadığı durumlarda n öğeden r öğe seçmenin yollarının sayısıdır. n! bölü r! çarpı (nr)! olarak hesaplanır. Örneğin, 5C3 10'a eşittir.

Kombinasyon algoritmaları, piyango oranlarında, takım veya komite seçiminde, makine öğreniminde özellik alt kümesi aramasında, test senaryosu oluşturmada ve parola veya anahtar alanı analizinde karşımıza çıkar. Sıralamaya önem vermeden bir grup seçtiğiniz her yerde kombinasyonlar geçerlidir.

Yapay zeka araçları, bir veri kümesinin tüm kombinasyonlarını oluşturabilir, tekrarları filtreleyebilir ve hatta büyük girdiler için en verimli yöntemi önerebilir. Bu zaman kazandırır, ancak doğruluğunu nCr formülüyle karşılaştırarak doğrulamanız gerekir.

Evet. Yapay zekâ kodlama asistanları C dilinde birleşik kod yazabilir. C++, Pythonve özyinelemeli ve dahil etme-hariç tutma yöntemleri de dahil olmak üzere diğer dilleri de kapsar. Çıktıyı her zaman test edin ve yinelenen öğeler veya r'nin n'den büyük olması gibi uç durumları kontrol edin.

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

Kombinasyon Nedir?

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

Yöntem-1: Özyinelemeli sabit eleman

Sözde Code

C/'de uygulamaC++

Uygulama Python

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

Sözde Code

C/'de uygulamaC++

Uygulama Python

Yinelenen Kombinasyonları İşleme

Sözlük veya sıralı olmayan harita kullanarak track tekrarlanan kombinasyonlar

İşte python'daki uygulama

SSS

Bu yazıyı şu şekilde özetleyin:

Haber bültenine kaydolun

Kombinasyon Nedir?

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

Yöntem-1: Özyinelemeli sabit eleman

Sözde Code

C/'de uygulamaC++

Uygulama Python

İLGİLİ MAKALELER

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

Sözde Code

C/'de uygulamaC++

Uygulama Python

Yinelenen Kombinasyonları İşleme

Sözlük veya sıralı olmayan harita kullanarak track tekrarlanan kombinasyonlar

İşte python'daki uygulama

SSS

Bu yazıyı şu şekilde özetleyin:

Haber bültenine kaydolun