Kombinatorik alqoritmlər

8.1 Kombinatorik alqoritmlərin tərifi.

Kombinatorik alqoritmlər — bunlar müxtəlif kombinatorik strukturların hesablanması, siyahıya alınması və yaradılması ilə bağlı məsələlərin həlli üçün nəzərdə tutulmuş alqoritmlərdir. Bu alqoritmlər çoxluqlar, alt çoxluqlar, permutasiyalar, kombinasiya və digər kombinatorik obyektlərlə işləmək üçün istifadə olunur.

Kombinatorik məsələlərin əsas növləri

• Permutasiyalar: Çoxluq elementlərinin bütün mümkün qaydada düzülən kombinasiyaları.
• Kombinasiyalar: Təyin olunmuş ölçüdə olan bütün mümkün qaydasız alt çoxluqlar.
• Yerləşmələr: Təyin olunmuş ölçüdə olan bütün mümkün qaydalı alt çoxluqlar.
• Bölüşdürmələr: Çoxluğu alt çoxluqlara bölməyin bütün mümkün yolları.
• Kombinatorik obyektlər: Qraflar, matrislər və s. kimi digər strukturlar.

Kombinatorik alqoritmlərin üstünlükləri və çatışmazlıqları

Üstünlükləri:

• Tam siyahılama: Bu alqoritmlər bütün mümkün kombinasiya variantlarını siyahıya ala bilir, bu isə tam axtarış (exhaustive search) məsələləri üçün faydalıdır.
• Çeviklik: Kombinatorik problemlərin geniş spektrini həll etmək üçün adaptasiya oluna bilər.
• Anlaşıqlıq: Rekursiv yanaşma və backtracking texnikasına görə çoxları üçün bu alqoritmləri başa düşmək və tətbiq etmək asandır.

Çatışmazlıqlar:

• Kombinator partlayış: Giriş məlumatlarının ölçüsü artdıqca, iş vaxtı və yaddaş həcmi kəskin şəkildə arta bilər (məsələn, O(n!)).
• Optimallıq olmaması: Kombinasiyaların sayı böyük olduqda bu alqoritmlər qeyri-effektiv ola bilər və daha inkişaf etmiş texnikalarla (məsələn, dinamik proqramlaşdırma və ya greedy alqoritmlər) əvəz olunmağı tələb edə bilər.

Kombinatorik alqoritmlərin zaman və yaddaş mürəkkəbliyi

Zaman mürəkkəbliyi:

• Permutasiyalar: O(n!), burada n — çoxluğun elementlərinin sayı.
• Kombinasiyalar: O(C(n, k)), burada C(n, k) — binom əmsalı, n! / (k! * (n - k)!) bərabərdir.
• Yerləşmələr: O(A(n, k)), burada A(n, k) — yerləşmələrin sayı, n! / (n - k)! bərabərdir.
• Alt çoxluqlar: O(2^n), çünki n elementlərinin hər biri alt çoxluğa daxil edilib-edilməməsi müəyyən olunur.

Yaddaş mürəkkəbliyi:

Adətən O(n) rekursiv quruluş prosesində aralıq nəticələrin saxlanılması üçün tələb olunur, lakin bütün nəticələrin saxlanılması üçün son yaddaş daha çox tələb oluna bilər (məsələn, permutasiyalar üçün O(n * n!)).

Kombinatorik alqoritmlərin nümunələri

8.2 Permutasiyaların generasiyası.

Vəzifə:

Verilmiş çoxluğun elementlərinin bütün unikal permutasiyalarını tapmaq.

Alqoritm:

Elementlərin bütün mümkün sıralanmış kombinasiyalarını generasiya etmək üçün rekursiya və ya iterativ metodlardan istifadə olunur.

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

print(permute([1, 2, 3]))

8.3 Kombinasiyaların generasiyası

Tapşırıq:

Təyin olunmuş ölçüdə olan bütün kombinasiyaları çoxluqdan tapmaq.

Alqoritm:

Təyin olunmuş ölçüdə olan bütün alt çoxluqları yaratmaq üçün rekursiya və ya iterasiya istifadə olunur.

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))
        

8.4 Cəmiyyətin bölünmələrinin yaradılması

Tapşırıq:

Cəmiyyəti altcəmiyyətlərə bölməyin mümkün olan bütün yollarını tap.

Algoritm:

Cəmiyyətin bütün mümkün bölünmələrini yaratmaq üçün rekursiya istifadə olunur.

import copy

def partition_set(s):
    result = []

    def backtrack(part, rest):
        if not rest:
            result.append(copy.deepcopy(part[:]))
            return
        for i in range(len(part)):
            part[i].append(rest[0])
            backtrack(part, rest[1:])
            part[i].pop()
        part.append([rest[0]])
        backtrack(part, rest[1:])
        part.pop()

    backtrack([], list(s))
    return result

print(partition_set({1, 2, 3}))
        
        

copy.deepcopy(part[:]) istifadə edilməsi part siyahısının dərin kopyasını yaradır. Bu, orijinal part ilə əlaqəsi olmayan yeni, müstəqil siyahı yaradır. Beləliklə, result içərisindəki hər bir element unikal bir bölünməni təmsil edir.