Python kursi/Standart kutubxona9/16-dars24 daqiqa

Mundarija (20)

15.9-dars: `itertools`: kombinatorika

15-QISM — STANDART KUTUBXONA · 9-dars

1. Kirish va motivatsiya

Ko'p vazifada barcha variantlarni ko'rib chiqish kerak bo'ladi:

Test: 3 ta brauzer × 3 ta operatsion tizim × 2 ta til — barcha birikmalar.
Turnir: 8 ta jamoaning har biri har biri bilan bir marta o'ynaydi — qancha o'yin?
Jamoa tuzish: 12 xodimdan barcha kerakli ko'nikmalarni qamraydigan ko'pi bilan 5 kishilik eng arzon guruh.
Marshrut: 6 ta do'konni aylanib chiqishning eng qisqa tartibi.

Bularni ichma-ich for tsikllar bilan yozish mumkin, lekin tsikllar soni o'zgaruvchan bo'lsa, kod tezda chalkashadi. itertools da buning uchun to'rtta tayyor funksiya bor: product, permutations, combinations, combinations_with_replacement.

Real vaziyat. Logistika startapi yetkazib berish marshrutini "hamma tartiblarni sinab ko'rish" usulida hisoblardi: min(permutations(manzillar), key=uzunlik). 8 ta manzil bilan hammasi zo'r ishladi — 40 320 variant, bir soniyadan kam. Bir kuni kuryerga 15 ta manzil berildi: variantlar soni 1,3 trillion bo'ldi va hisob-kitob, taxminan, bir necha kun davom etishi kerak edi. Server "osilib qoldi", kuryer esa yo'lga chiqmadi.

Bu darsda kombinatorik iteratorlarni, ularning matematik formulalarini va eng muhimi — variantlar sonining portlovchi o'sishini oldindan hisoblashni o'rganamiz.

Bu darsda:

product — Dekart ko'paytma, ichma-ich tsikllar o'rnida
permutations — tartib muhim
combinations va combinations_with_replacement — tartib muhim emas
math.comb, math.perm, math.factorial — sanash, yaratmasdan
Takrorlangan elementlar va "pozitsiya bo'yicha" tanlash
product kirishni oldindan to'liq o'qiydi
Kombinatorik portlash — qachon to'liq qidiruv mumkin emas
Amaliy: jamoa tanlash — to'liq qidiruv, kesish va ochko'z usul

2. Nazariya — chuqur tushuntirish

2.1. To'rt funksiya

Funksiya	Soni	Misol (`"abc"`, 2)
`product(a, b)` / `product(s, repeat=k)`	`n^k`	`aa ab ac ba bb bc ca cb cc`
`permutations(s, k)`	`n! / (n-k)!`	`ab ac ba bc ca cb`
`combinations(s, k)`	`n! / (k!(n-k)!)`	`ab ac bc`
`combinations_with_replacement(s, k)`	`(n+k-1)! / (k!(n-1)!)`	`aa ab ac bb bc cc`

python

from itertools import product, permutations, combinations

product("ab", [1, 2])            # ('a', 1), ('a', 2), ('b', 1), ('b', 2)
product(range(10), repeat=4)     # 0000 ... 9999 — 10 000 ta
permutations("abc")              # k berilmasa — k = n
combinations("abcd", 2)          # 6 ta

product — ichma-ich tsikllar o'rnida:

python

for a in A:
    for b in B:
        for c in C: ...
# ≡
for a, b, c in product(A, B, C): ...

2.2. Sanash — yaratmasdan

Funksiya	Ma'nosi
`math.factorial(n)`	`n!`
`math.perm(n, k)`	Tartibli tanlovlar soni
`math.comb(n, k)`	Tartibsiz tanlovlar soni
`k > n`	`comb` va `perm` → `0`

Qoida: avval sanang, keyin yarating. math.comb(40, 5) bir zumda 658 008 deydi — shu raqamga qarab to'liq qidiruv mumkinmi, hal qilinadi.

2.3. Chegara holatlar va natija tartibi

Holat	Natija
`combinations(s, 0)`	`[()]` — bitta bo'sh tanlov
`combinations(s, k)`, `k > len(s)`	`[]`
`product()`	`[()]`
Natija tartibi	Leksikografik — kirish pozitsiyalari bo'yicha

Elementlar qiymati emas, pozitsiyasi bo'yicha tanlanadi:

python

list(combinations([3, 1, 2], 2))     # [(3, 1), (3, 2), (1, 2)] — saralanmagan
list(permutations("aab", 2))         # 6 ta, ('a', 'a') ikki marta!
len(set(permutations("aab")))        # 3 — noyoblari

Takrorlangan elementlardan noyob natija kerak bo'lsa — set(...) (kichik hajmda) yoki kirishni avval noyob qilish.

2.4. Dangasalik chegaralari

Funksiya	Kirish	Chiqish
`product`, `permutations`, `combinations`	Oldindan to'liq o'qiladi (ichida `tuple` ga aylantiriladi)	Dangasa — bittadan

Oqibatlari:

Cheksiz iterator (count()) berilsa — abadiy osilib qoladi.
Katta generator berilsa — hammasi xotiraga tushadi.
Chiqish esa dangasa: next(permutations(range(20))) darhol ishlaydi, garchi jami 2,4 × 10¹⁸ ta bo'lsa ham.

2.5. Kombinatorik portlash

`n`	`n!` (permutations)	`2^n` (barcha qism to'plamlar)	`C(n, n/2)`
5	120	32	10
10	3 628 800	1 024	252
15	1 307 674 368 000	32 768	6 435
20	2,4 × 10¹⁸	1 048 576	184 756
30	2,7 × 10³²	1 073 741 824	155 117 520

Taxminiy qoida (sof Python, bitta yadro, har variant uchun oddiy hisob): soniyasiga 1–10 million variant.

Variantlar	To'liq qidiruv
≤ 10⁶	Soniyalar
10⁷–10⁸	Daqiqalar — kesish (pruning) yoki optimallashtirish
≥ 10⁹	Boshqa algoritm: dinamik dasturlash, ochko'z usul, evristika, maxsus kutubxona

Taxminiy vaqtni kichik n da o'lchab, formula bilan katta n ga ko'paytiring (Misol 2).

2.6. Keng tarqalgan andozalar

Vazifa	Yechim	Soni
Barcha qism to'plamlar	`chain.from_iterable(combinations(s, r) for r in range(len(s)+1))`	`2^n`
Barcha juftliklar (har biri har biri bilan)	`combinations(s, 2)`	`n(n-1)/2`
Kod/parol variantlari	`product(alifbo, repeat=k)`	`len(alifbo)^k`
Parametrlar to'ri (grid)	`product(*qiymatlar)`	Ko'paytma
Marshrut, boshlang'ich nuqta qat'iy	`permutations(qolganlar)`	`(n-1)!`
Yig'indisi `S` bo'lgan tanlovlar	`combinations` + filtr	`C(n, k)`

3. Tez ma'lumotnoma

python

import itertools as it
import math

it.product(A, B, C)                       # ichma-ich tsikllar
it.product("01", repeat=8)                # 8 bitli barcha satrlar
it.permutations(s, k)                     # tartibli
it.combinations(s, k)                     # tartibsiz
it.combinations_with_replacement(s, k)    # takrorlanadigan, tartibsiz

math.comb(n, k); math.perm(n, k); math.factorial(n)   # avval sanang

Qoidalar

avval math.comb/perm bilan sanang
tartib muhim — permutations, muhim emas — combinations
tanlov pozitsiya bo'yicha — takrorlar natijada ham takrorlanadi
kirish oldindan o'qiladi — cheksiz iterator bermang
10^7 dan ko'p variant — kesish yoki boshqa algoritm

4. Batafsil misollar

Misol 1 — To'rt funksiya va formulalar

python

"""product, permutations, combinations, combinations_with_replacement; soni formulalar bilan mosligi; chegara holatlar; pozitsiya bo'yicha tanlash va takrorlar."""

import itertools as it
import math


def main() -> None:
    s = "abcd"
    n, k = len(s), 2

    print(f"=== 1. '{s}' dan {k} ta ===")
    variantlar = [
        ("product(repeat=2)", list(it.product(s, repeat=k)), n ** k),
        ("permutations", list(it.permutations(s, k)), math.perm(n, k)),
        ("combinations", list(it.combinations(s, k)), math.comb(n, k)),
        ("combinations_with_replacement", list(it.combinations_with_replacement(s, k)), math.comb(n + k - 1, k)),
    ]
    for nom, natija, formula in variantlar:
        namuna = " ".join("".join(t) for t in natija[:8])
        print(f"  {nom:30} {len(natija):>3} ta (formula: {formula})  {namuna}{' ...' if len(natija) > 8 else ''}")

    print("\n=== 2. product — ichma-ich tsikllar o'rnida ===")
    brauzerlar, tizimlar, tillar = ["Chrome", "Firefox"], ["Windows", "Linux", "macOS"], ["uz", "ru"]
    ichma_ich = [(b, t, l) for b in brauzerlar for t in tizimlar for l in tillar]
    birikmalar = list(it.product(brauzerlar, tizimlar, tillar))
    print(f"  test birikmalari: {len(birikmalar)} ta, birinchisi {birikmalar[0]}")
    print(f"  ichma-ich tsikllar bilan bir xil: {ichma_ich == birikmalar}")
    print(f"  PIN kodlar (4 xona): {math.prod([10] * 4)} = {sum(1 for _ in it.product(range(10), repeat=4))}")

    print("\n=== 3. Chegara holatlar ===")
    print(f"  combinations('abc', 0): {list(it.combinations('abc', 0))}")
    print(f"  combinations('ab', 3):  {list(it.combinations('ab', 3))}")
    print(f"  product():              {list(it.product())}")
    print(f"  math.comb(3, 5) = {math.comb(3, 5)}, math.perm(3, 5) = {math.perm(3, 5)}")

    print("\n=== 4. ⚠️ Pozitsiya bo'yicha tanlash ===")
    print(f"  combinations([3, 1, 2], 2): {list(it.combinations([3, 1, 2], 2))}  ← kirish tartibida")
    takrorli = list(it.permutations("aab"))
    print(f"  permutations('aab'): {len(takrorli)} ta, noyobi {len(set(takrorli))} ta")
    print(f"  {[''.join(p) for p in takrorli]}")
    print(f"  noyoblar: {sorted(''.join(p) for p in set(takrorli))}")
    print(f"  formula: 3! / 2! = {math.factorial(3) // math.factorial(2)}")

    print("\n=== 5. Barcha qism to'plamlar ===")
    elementlar = ["non", "sut", "tuxum"]
    qism = list(it.chain.from_iterable(it.combinations(elementlar, r) for r in range(len(elementlar) + 1)))
    print(f"  {len(qism)} ta = 2^{len(elementlar)}")
    for q in qism:
        print(f"    {q}")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. 'abcd' dan 2 ta ===
  product(repeat=2)               16 ta (formula: 16)  aa ab ac ad ba bb bc bd ...
  permutations                    12 ta (formula: 12)  ab ac ad ba bc bd ca cb ...
  combinations                     6 ta (formula: 6)  ab ac ad bc bd cd
  combinations_with_replacement   10 ta (formula: 10)  aa ab ac ad bb bc bd cc ...

=== 2. product — ichma-ich tsikllar o'rnida ===
  test birikmalari: 12 ta, birinchisi ('Chrome', 'Windows', 'uz')
  ichma-ich tsikllar bilan bir xil: True
  PIN kodlar (4 xona): 10000 = 10000

=== 3. Chegara holatlar ===
  combinations('abc', 0): [()]
  combinations('ab', 3):  []
  product():              [()]
  math.comb(3, 5) = 0, math.perm(3, 5) = 0

=== 4. ⚠️ Pozitsiya bo'yicha tanlash ===
  combinations([3, 1, 2], 2): [(3, 1), (3, 2), (1, 2)]  ← kirish tartibida
  permutations('aab'): 6 ta, noyobi 3 ta
  ['aab', 'aba', 'aab', 'aba', 'baa', 'baa']
  noyoblar: ['aab', 'aba', 'baa']
  formula: 3! / 2! = 3

=== 5. Barcha qism to'plamlar ===
  8 ta = 2^3
    ()
    ('non',)
    ('sut',)
    ('tuxum',)
    ('non', 'sut')
    ('non', 'tuxum')
    ('sut', 'tuxum')
    ('non', 'sut', 'tuxum')

Nima ko'rsatdi: 2.1, 2.2, 2.3-bo'limlar.

Misol 2 — Portlovchi o'sish va dangasalik chegaralari

python

"""n! va 2^n o'sish jadvali; kichik n da o'lchab katta n uchun vaqtni bashorat qilish; chiqish dangasa, kirish esa to'liq o'qiladi; product va cheksiz iterator."""

import itertools as it
import math
import time
import tracemalloc


def main() -> None:
    print("=== 1. O'sish jadvali ===")
    print(f"  {'n':>3} {'n!':>36} {'2^n':>14} {'C(n, n/2)':>12}")
    for n in (5, 10, 15, 20, 25):
        print(f"  {n:>3} {math.factorial(n):>36,} {2 ** n:>14,} {math.comb(n, n // 2):>12,}".replace(",", " "))

    print("\n=== 2. Vaqtni bashorat qilish ===")
    bosh = time.perf_counter()
    soni = sum(1 for _ in it.permutations(range(9)))
    vaqt_9 = time.perf_counter() - bosh
    tezlik = soni / vaqt_9
    print(f"  permutations(9): {soni:,} ta".replace(",", " "))
    print(f"  soniyasiga 1 mln dan ko'p variant: {tezlik > 1_000_000}")
    for n in (12, 15, 20):
        taxmin = math.factorial(n) / tezlik
        if taxmin < 3600:
            birlik = "soatdan kam"
        elif taxmin < 86_400 * 365:
            birlik = "soatlar–kunlar"
        else:
            birlik = "yillar va undan ko'p"
        print(f"  n={n}: {math.factorial(n):,} variant → {birlik}".replace(",", " "))

    print("\n=== 3. Chiqish dangasa ===")
    bosh = time.perf_counter()
    birinchi = next(it.permutations(range(20)))
    print(f"  next(permutations(range(20)))[:5] = {birinchi[:5]}, 10 ms dan tez: {time.perf_counter() - bosh < 0.01}")
    print(f"  birinchi 3 ta kombinatsiya C(60, 5) dan: {list(it.islice(it.combinations(range(60), 5), 3))}")

    print("\n=== 4. ⚠️ Kirish esa oldindan o'qiladi ===")
    jurnal: list[str] = []

    def manba():
        for x in "abc":
            jurnal.append(x)
            yield x

    birikmalar = it.product(manba(), [1, 2])
    print(f"  product yaratildi, next() chaqirilmadi — manba o'qildi: {jurnal}")

    tracemalloc.start()
    katta = it.product(range(200_000), "xy")
    _, cho_qqi = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    print(f"  product(range(200 000), 'xy') yaratishning o'zi 1 MB dan ko'p xotira: {cho_qqi > 1_000_000}")
    print("  ⚠️ product(itertools.count(), ...) — abadiy osilib qoladi")
    del birikmalar, katta


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. O'sish jadvali ===
    n                                   n!            2^n    C(n, n/2)
    5                                  120             32           10
   10                            3 628 800          1 024          252
   15                    1 307 674 368 000         32 768        6 435
   20            2 432 902 008 176 640 000      1 048 576      184 756
   25   15 511 210 043 330 985 984 000 000     33 554 432    5 200 300

=== 2. Vaqtni bashorat qilish ===
  permutations(9): 362 880 ta
  soniyasiga 1 mln dan ko'p variant: True
  n=12: 479 001 600 variant → soatdan kam
  n=15: 1 307 674 368 000 variant → soatlar–kunlar
  n=20: 2 432 902 008 176 640 000 variant → yillar va undan ko'p

=== 3. Chiqish dangasa ===
  next(permutations(range(20)))[:5] = (0, 1, 2, 3, 4), 10 ms dan tez: True
  birinchi 3 ta kombinatsiya C(60, 5) dan: [(0, 1, 2, 3, 4), (0, 1, 2, 3, 5), (0, 1, 2, 3, 6)]

=== 4. ⚠️ Kirish esa oldindan o'qiladi ===
  product yaratildi, next() chaqirilmadi — manba o'qildi: ['a', 'b', 'c']
  product(range(200 000), 'xy') yaratishning o'zi 1 MB dan ko'p xotira: True
  ⚠️ product(itertools.count(), ...) — abadiy osilib qoladi

Nima ko'rsatdi: 2.4, 2.5-bo'limlar.

Misol 3 — Amaliy andozalar

python

"""Turnir jadvali; parol maydoni va entropiya; tanga bilan summa to'lash usullari; parametrlar to'ri; kichik marshrut masalasi — boshlang'ich nuqta qat'iy."""

import itertools as it
import math

MASOFA = {
    ("Ombor", "Chilonzor"): 9, ("Ombor", "Yunusobod"): 12, ("Ombor", "Sergeli"): 14, ("Ombor", "Olmazor"): 7,
    ("Chilonzor", "Yunusobod"): 15, ("Chilonzor", "Sergeli"): 8, ("Chilonzor", "Olmazor"): 6,
    ("Yunusobod", "Sergeli"): 20, ("Yunusobod", "Olmazor"): 10, ("Sergeli", "Olmazor"): 13,
}


def masofa(a: str, b: str) -> int:
    return MASOFA.get((a, b)) or MASOFA[(b, a)]


def main() -> None:
    print("=== 1. Turnir: har jamoa har biri bilan bir marta ===")
    jamoalar = ["Paxtakor", "Andijon", "Nasaf", "Navbahor", "Bunyodkor", "AGMK", "Qizilqum", "Sogdiana"]
    oyinlar = list(it.combinations(jamoalar, 2))
    print(f"  {len(jamoalar)} jamoa → {len(oyinlar)} o'yin (formula n(n-1)/2 = {len(jamoalar) * (len(jamoalar) - 1) // 2})")
    print(f"  birinchi 3: {oyinlar[:3]}")
    uy_mehmon = list(it.permutations(jamoalar, 2))
    print(f"  uy va mehmon o'yinlari bilan: {len(uy_mehmon)}")

    print("\n=== 2. Parol maydoni ===")
    for nom, alifbo, uzunlik in (("PIN, 4 raqam", 10, 4), ("kichik harflar, 8", 26, 8),
                                 ("harf+raqam+belgi, 12", 26 + 26 + 10 + 32, 12)):
        variantlar = alifbo ** uzunlik
        print(f"  {nom:22} {variantlar:.2e} variant, entropiya {math.log2(variantlar):.1f} bit")

    print("\n=== 3. Tangalar bilan 1 000 so'm to'lash ===")
    tangalar = [100, 200, 500]
    usullar = set()
    for soni in range(1, 11):
        for tanlov in it.combinations_with_replacement(tangalar, soni):
            if sum(tanlov) == 1000:
                usullar.add(tanlov)
    for usul in sorted(usullar, key=len):
        print(f"  {len(usul):>2} ta tanga: {usul}")

    print("\n=== 4. Parametrlar to'ri ===")
    tor = {"o'rganish_tezligi": [0.1, 0.01], "qatlamlar": [2, 3, 4], "dropout": [0.0, 0.5]}
    tajribalar = [dict(zip(tor, qiymatlar)) for qiymatlar in it.product(*tor.values())]
    print(f"  {len(tajribalar)} ta tajriba = {' × '.join(str(len(v)) for v in tor.values())}")
    print(f"  birinchisi: {tajribalar[0]}")
    print(f"  oxirgisi:   {tajribalar[-1]}")

    print("\n=== 5. Kuryer marshruti (ombordan chiqib, qaytib keladi) ===")
    manzillar = ["Chilonzor", "Yunusobod", "Sergeli", "Olmazor"]

    def uzunlik(tartib: tuple[str, ...]) -> int:
        yol = ("Ombor", *tartib, "Ombor")
        return sum(masofa(a, b) for a, b in it.pairwise(yol))

    barcha = list(it.permutations(manzillar))
    eng_yaxshi = min(barcha, key=uzunlik)
    eng_yomon = max(barcha, key=uzunlik)
    print(f"  variantlar: {len(barcha)} = {len(manzillar)}!")
    print(f"  eng qisqa: Ombor → {' → '.join(eng_yaxshi)} → Ombor = {uzunlik(eng_yaxshi)} km")
    print(f"  eng uzun:  {uzunlik(eng_yomon)} km")
    print(f"  teskari yo'nalish ham xuddi shunday uzunlikda: {uzunlik(eng_yaxshi[::-1]) == uzunlik(eng_yaxshi)}")
    print(f"  ⭐ shuning uchun haqiqiy noyob marshrutlar: {math.factorial(len(manzillar)) // 2}")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. Turnir: har jamoa har biri bilan bir marta ===
  8 jamoa → 28 o'yin (formula n(n-1)/2 = 28)
  birinchi 3: [('Paxtakor', 'Andijon'), ('Paxtakor', 'Nasaf'), ('Paxtakor', 'Navbahor')]
  uy va mehmon o'yinlari bilan: 56

=== 2. Parol maydoni ===
  PIN, 4 raqam           1.00e+04 variant, entropiya 13.3 bit
  kichik harflar, 8      2.09e+11 variant, entropiya 37.6 bit
  harf+raqam+belgi, 12   4.76e+23 variant, entropiya 78.7 bit

=== 3. Tangalar bilan 1 000 so'm to'lash ===
   2 ta tanga: (500, 500)
   4 ta tanga: (100, 200, 200, 500)
   5 ta tanga: (100, 100, 100, 200, 500)
   5 ta tanga: (200, 200, 200, 200, 200)
   6 ta tanga: (100, 100, 100, 100, 100, 500)
   6 ta tanga: (100, 100, 200, 200, 200, 200)
   7 ta tanga: (100, 100, 100, 100, 200, 200, 200)
   8 ta tanga: (100, 100, 100, 100, 100, 100, 200, 200)
   9 ta tanga: (100, 100, 100, 100, 100, 100, 100, 100, 200)
  10 ta tanga: (100, 100, 100, 100, 100, 100, 100, 100, 100, 100)

=== 4. Parametrlar to'ri ===
  12 ta tajriba = 2 × 3 × 2
  birinchisi: {"o'rganish_tezligi": 0.1, 'qatlamlar': 2, 'dropout': 0.0}
  oxirgisi:   {"o'rganish_tezligi": 0.01, 'qatlamlar': 4, 'dropout': 0.5}

=== 5. Kuryer marshruti (ombordan chiqib, qaytib keladi) ===
  variantlar: 24 = 4!
  eng qisqa: Ombor → Yunusobod → Olmazor → Chilonzor → Sergeli → Ombor = 50 km
  eng uzun:  64 km
  teskari yo'nalish ham xuddi shunday uzunlikda: True
  ⭐ shuning uchun haqiqiy noyob marshrutlar: 12

Nima ko'rsatdi: 2.1, 2.6-bo'limlar.

Misol 4 — Amaliy: loyiha jamoasini tanlash

Vazifa: xodimlar orasidan barcha kerakli ko'nikmalarni qamraydigan, ko'pi bilan 5 kishilik, eng kam maoshli jamoa. Uch usulni solishtiramiz: to'liq qidiruv (combinations), kesish bilan to'liq qidiruv (qimmatlari tekshirilmaydi) va ochko'z usul (tez, lekin eng yaxshisini kafolatlamaydi). Oxirida xodimlar soni oshganda variantlar soni qanday portlashini math.comb bilan hisoblaymiz.

python

"""Qamrov masalasi: combinations bilan to'liq qidiruv; kesish; ochko'z usul; natijalarni solishtirish; math.comb bilan portlashni oldindan baholash."""

import itertools as it
import math
from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class Xodim:
    ism: str
    maosh: int
    konikmalar: frozenset[str]


XODIMLAR = [
    Xodim("Aziz", 18, frozenset({"python", "sql"})),
    Xodim("Malika", 22, frozenset({"python", "ml", "sql"})),
    Xodim("Bek", 15, frozenset({"frontend", "dizayn"})),
    Xodim("Nodira", 25, frozenset({"devops", "python", "xavfsizlik"})),
    Xodim("Sardor", 12, frozenset({"frontend"})),
    Xodim("Dilnoza", 20, frozenset({"ml", "tahlil"})),
    Xodim("Jasur", 17, frozenset({"devops", "sql"})),
    Xodim("Kamola", 14, frozenset({"dizayn", "tahlil"})),
    Xodim("Otabek", 40, frozenset({"python", "ml", "devops", "xavfsizlik"})),
    Xodim("Zarina", 16, frozenset({"xavfsizlik", "sql"})),
    Xodim("Rustam", 11, frozenset({"tahlil"})),
    Xodim("Laylo", 19, frozenset({"frontend", "python"})),
]
KERAK = frozenset({"python", "ml", "frontend", "devops", "xavfsizlik", "dizayn"})


def qamraydimi(jamoa: tuple[Xodim, ...]) -> bool:
    return KERAK <= frozenset().union(*(x.konikmalar for x in jamoa))


def maosh(jamoa: tuple[Xodim, ...]) -> int:
    return sum(x.maosh for x in jamoa)


def toliq(xodimlar: list[Xodim]) -> tuple[tuple[Xodim, ...] | None, int]:
    eng, tekshirildi = None, 0
    for hajm in range(1, 6):
        for jamoa in it.combinations(xodimlar, hajm):
            tekshirildi += 1
            if qamraydimi(jamoa) and (eng is None or maosh(jamoa) < maosh(eng)):
                eng = jamoa
    return eng, tekshirildi


def kesish_bilan(xodimlar: list[Xodim]) -> tuple[tuple[Xodim, ...] | None, int]:
    arzondan = sorted(xodimlar, key=lambda x: x.maosh)
    eng, tekshirildi = None, 0
    for hajm in range(1, 6):
        for jamoa in it.combinations(arzondan, hajm):
            if eng is not None and maosh(jamoa) >= maosh(eng):
                continue                               # qimmat — qamrovni tekshirmaymiz
            tekshirildi += 1
            if qamraydimi(jamoa):
                eng = jamoa
    return eng, tekshirildi


def ochkoz(xodimlar: list[Xodim]) -> tuple[Xodim, ...]:
    qolgan, jamoa = set(KERAK), []
    while qolgan:
        eng = max(xodimlar, key=lambda x: (len(x.konikmalar & qolgan) / x.maosh, x.ism))
        jamoa.append(eng)
        qolgan -= eng.konikmalar
    return tuple(jamoa)


def korsat(nom: str, jamoa: tuple[Xodim, ...] | None, tekshirildi: int | None = None) -> None:
    assert jamoa is not None
    ismlar = ", ".join(x.ism for x in jamoa)
    qoshimcha = f", tekshirildi {tekshirildi}" if tekshirildi is not None else ""
    print(f"  {nom:14} [{ismlar}] maosh={maosh(jamoa)} qamrov={qamraydimi(jamoa)}{qoshimcha}")


def main() -> None:
    print(f"=== 1. {len(XODIMLAR)} xodim, kerakli ko'nikmalar: {sorted(KERAK)} ===")
    jami = sum(math.comb(len(XODIMLAR), h) for h in range(1, 6))
    print(f"  1–5 kishilik jamoalar soni: {jami} (C(12,1) + ... + C(12,5))")

    print("\n=== 2. Uch usul ===")
    toliq_natija, toliq_soni = toliq(XODIMLAR)
    kesish_natija, kesish_soni = kesish_bilan(XODIMLAR)
    ochkoz_natija = ochkoz(XODIMLAR)
    korsat("to'liq", toliq_natija, toliq_soni)
    korsat("kesish bilan", kesish_natija, kesish_soni)
    korsat("ochko'z", ochkoz_natija)

    print("\n=== 3. Solishtirish ===")
    assert toliq_natija is not None and kesish_natija is not None
    print(f"  to'liq va kesish bir xil maosh: {maosh(toliq_natija) == maosh(kesish_natija)}")
    print(f"  kesish kamroq jamoani tekshirdi: {kesish_soni < toliq_soni}")
    print(f"  ochko'z eng arzonini topdimi: {maosh(ochkoz_natija) == maosh(toliq_natija)}")
    print(f"  ochko'z ortiqcha to'lov: {maosh(ochkoz_natija) - maosh(toliq_natija)}")

    print("\n=== 4. Xodimlar ko'paysa ===")
    for n in (12, 40, 200, 1000):
        soni = sum(math.comb(n, h) for h in range(1, 6))
        holat = "✅ soniyalar" if soni <= 10 ** 6 else ("⚠️ daqiqalar" if soni <= 10 ** 8 else "❌ to'liq qidiruv mumkin emas")
        print(f"  n={n:>4}: {soni:>18,} jamoa  {holat}".replace(",", " "))
    print("  ⭐ katta n uchun: ochko'z usul, butun sonli dasturlash (OR-Tools) yoki evristika")


if __name__ == "__main__":
    main()

Natijaning muhim qismi:

text

=== 1. 12 xodim, kerakli ko'nikmalar: ['devops', 'dizayn', 'frontend', 'ml', 'python', 'xavfsizlik'] ===
  1–5 kishilik jamoalar soni: 1585 (C(12,1) + ... + C(12,5))

=== 2. Uch usul ===
  to'liq         [Bek, Otabek] maosh=55 qamrov=True, tekshirildi 1585
  kesish bilan   [Bek, Otabek] maosh=55 qamrov=True, tekshirildi 187
  ochko'z        [Bek, Nodira, Dilnoza] maosh=60 qamrov=True

=== 3. Solishtirish ===
  to'liq va kesish bir xil maosh: True
  kesish kamroq jamoani tekshirdi: True
  ochko'z eng arzonini topdimi: False
  ochko'z ortiqcha to'lov: 5

=== 4. Xodimlar ko'paysa ===
  n=  12:              1 585 jamoa  ✅ soniyalar
  n=  40:            760 098 jamoa  ✅ soniyalar
  n= 200:      2 601 668 490 jamoa  ❌ to'liq qidiruv mumkin emas
  n=1000:  8 291 875 042 450 jamoa  ❌ to'liq qidiruv mumkin emas
  ⭐ katta n uchun: ochko'z usul, butun sonli dasturlash (OR-Tools) yoki evristika

Nima ko'rsatdi: 2.2, 2.5, 2.6-bo'limlar.

5. To'g'ri va noto'g'ri tushunishlar

Noto'g'ri fikr	To'g'risi
"`combinations` qiymatlarni saralab beradi"	Kirish pozitsiyalari tartibida
"`permutations('aab')` — noyob tartiblar"	Takrorlar bilan 6 ta, noyobi 3 ta
"`product` to'liq dangasa"	Kirish oldindan o'qiladi, chiqish dangasa
"`combinations(s, 0)` — bo'sh ro'yxat"	`[()]` — bitta bo'sh tanlov
"12 ta element — oz, hammasini sinash mumkin"	`12!` ≈ 479 mln — daqiqalar
"Kompyuter tez — 20! ni ham sinaydi"	Yillar
"Tezroq kompyuter muammoni hal qiladi"	Har +1 element vaqtni `n` barobar oshiradi
"Ochko'z usul doim eng yaxshisini topadi"	Tez, lekin kafolatsiz

6. Keng tarqalgan xatolar va yechimlari

1. Sanamasdan yaratish

python

min(permutations(manzillar), key=uzunlik)          # ❌ 15 manzil — kunlar
if math.factorial(len(manzillar)) > 10**7: ...     # ✅ boshqa algoritmga o'tish

2. Ichma-ich tsikllar soni o'zgaruvchan

python

for a in A: for b in B: ...                         # ❌ o'lcham kodda qotib qolgan
for birikma in product(*ro_yxatlar): ...            # ✅

3. permutations bilan tartibsiz tanlov

python

juftlar = permutations(jamoalar, 2)                 # ❌ har juft ikki marta
juftlar = combinations(jamoalar, 2)                 # ✅

4. Takrorli kirishdan noyob natija kutish

python

permutations("aabb")                                # ⚠️ 24 ta, noyobi 6
set(permutations("aabb"))                           # ✅ kichik n uchun

5. Cheksiz yoki katta generatorni kirish sifatida

python

product(itertools.count(), "ab")                    # ❌ osilib qoladi

6. Natijani ro'yxatga yig'ish

python

barcha = list(combinations(range(60), 5))           # ❌ 5,4 mln kortej xotirada
for jamoa in combinations(range(60), 5): ...        # ✅ dangasa

7. Marshrutda simmetriyani hisobga olmaslik

python

permutations(barcha_nuqtalar)                       # ⚠️ n! — boshlanish va yo'nalish takrorlanadi
permutations(nuqtalar[1:])                          # ✅ (n-1)!, yana /2 teskari yo'nalish

8. Kesishsiz to'liq qidiruv

python

for jamoa in combinations(xodimlar, k):
    if qamraydimi(jamoa) and maosh(jamoa) < eng: ...   # ⚠️ qimmatlari ham tekshiriladi
    # ✅ avval arzon shartni tekshiring

7. Integratsiya — bu bilim qayerda kerak bo'ladi

6-qism (o'tilgan): set amallari — qamrov tekshiruvi
15.8-dars (o'tilgan): dangasa iteratorlar, islice, chain
15.10-dars: functools.cache — takroriy hisoblarni keshlash
17.10-dars: hypothesis — kombinatsiyalar o'rniga tasodifiy sinovlar
24-qism: parametrlar to'ri, pandas bilan tajriba natijalari
31.10-dars: texnik intervyu — algoritmlar: dinamik dasturlash, orqaga qaytish
25.4-dars: modelni baholash — giperparametr qidiruvi

8. Eng yaxshi amaliyotlar

Avval sanang: math.comb, math.perm, math.factorial.
Kichik n da o'lchab, katta n uchun vaqtni bashorat qiling.
To'g'ri funksiyani tanlang: tartib va takrorlanish muhimmi?
Natijalarni ro'yxatga yig'mang — dangasa aylaning.
Arzon tekshiruvlarni oldinga qo'ying — kesish.
Simmetriyani yo'qoting — qat'iy boshlang'ich nuqta, teskari yo'nalish.
Portlash chegarasida algoritmni almashtiring — ochko'z, dinamik dasturlash, maxsus kutubxona.
Chegara holatlarini tekshiring: k = 0, k > n, bo'sh kirish.

9. Amaliy topshiriq

Vazifa 1: Natijani bashorat qiling

python

import itertools as it, math
1.  print(len(list(it.product("ab", repeat=3))))
2.  print(list(it.permutations("ab")))
3.  print(len(list(it.combinations(range(5), 3))))
4.  print(list(it.combinations_with_replacement("ab", 2)))
5.  print(math.comb(6, 2), math.perm(6, 2))
6.  print(list(it.combinations("abc", 0)))
7.  print(list(it.combinations([2, 1], 2)))
8.  print(len(set(it.permutations("aa"))))
9.  print(math.comb(4, 7))
10. print(next(it.product("xy", [1, 2])))
11. print(len(list(it.product([1, 2], "ab", [True]))))
12. print(math.factorial(0))

Javoblar

8
[('a', 'b'), ('b', 'a')]
10
[('a', 'a'), ('a', 'b'), ('b', 'b')]
15 30
[()]
[(2, 1)]
1
0
('x', 1)
4
1

Vazifa 2: Xatolarni tuzating

python

1.  def oyinlar(jamoalar):
        return list(itertools.permutations(jamoalar, 2))     # har juft bir marta o'ynaydi

2.  def eng_qisqa(nuqtalar):                                 # 14 ta nuqta
        return min(itertools.permutations(nuqtalar), key=uzunlik)

3.  def barcha_parollar(alifbo, uzunlik):
        return [("".join(p)) for p in itertools.product(alifbo, repeat=uzunlik)]   # 62 belgi, 8 uzunlik

4.  def noyob_sozlar(harflar):
        return list(itertools.permutations(harflar))         # "kitob" dan noyob so'zlar

5.  def tanlovlar(elementlar):
        return itertools.combinations(sorted(elementlar), len(elementlar) + 1)

Javoblar

python

1.  def oyinlar(jamoalar):
        return list(itertools.combinations(jamoalar, 2))

2.  def eng_qisqa(nuqtalar):
        n = len(nuqtalar)
        if math.factorial(n - 1) // 2 > 10**7:
            return ochkoz_marshrut(nuqtalar)                # yoki dinamik dasturlash (Held–Karp)
        boshi, qolgan = nuqtalar[0], nuqtalar[1:]
        return min(((boshi, *p) for p in itertools.permutations(qolgan)), key=uzunlik)

3.  # 62^8 ≈ 2,18 × 10^14 — ro'yxat imkonsiz; faqat dangasa va chegara bilan
    def parollar(alifbo, uzunlik):
        return ("".join(p) for p in itertools.product(alifbo, repeat=uzunlik))

4.  def noyob_sozlar(harflar):
        return sorted({"".join(p) for p in itertools.permutations(harflar)})

5.  def tanlovlar(elementlar):                               # barcha qism to'plamlar
        return itertools.chain.from_iterable(
            itertools.combinations(elementlar, r) for r in range(len(elementlar) + 1)
        )

Vazifa 3: Kombinatorik funksiyalarni o'zingiz yozing

Faqat rekursiya yoki generatorlar bilan (itertools siz):

mening_product(*ketma_ketliklar, repeat=1)
mening_permutations(s, k)
mening_combinations(s, k)
Natijalar tartibi ham itertools bilan bir xil ekanini 50 ta tasodifiy kirishda tekshiring
Tezlikni solishtiring

Vazifa 4: Sudoku yordamchisi

4×4 sudoku uchun har bo'sh katakka mumkin bo'lgan raqamlar
Har qator uchun to'ldirish variantlarini permutations bilan yarating va noto'g'rilarini filtrlang
product bilan qatorlar birikmalarini tekshirib, yechimni toping
Variantlar sonini har bosqichda chop eting va 9×9 da nega bu usul ishlamasligini hisoblang

Vazifa 5: Menyu tuzish

Oshxona: 5 salat, 6 asosiy taom, 4 shirinlik — narxi va kaloriyasi bilan
Byudjet va kaloriya chegarasi ichidagi barcha tushlik birikmalari (product)
Guruh uchun: 3 kishiga har xil asosiy taomlar (combinations) — umumiy narx minimal
Natijalarni narx bo'yicha saralab, eng yaxshi 5 tasini chiqaring

Vazifa 6: Qopdagi yuklar (knapsack)

15 ta buyum (og'irlik, qiymat), qop sig'imi 50 kg
To'liq qidiruv: barcha qism to'plamlar (2^15)
Dinamik dasturlash yechimi — natijalar bir xil ekanini tekshiring
30 va 60 buyum uchun ikkala usul vaqtini o'lchang yoki bashorat qiling

Vazifa 7: O'ylash

Kombinatorik portlash — ko'p "oddiy ko'rinadigan" masalalarning (marshrut, jadval tuzish, qopdagi yuklar) nega amalda qiyinligini tushuntiradi. Bu masalalar NP-qiyin deb ataladi. Nega kompyuterlar tezlashsa ham ular "yechilmaydi" va amaliyotda logistika, aviakompaniyalar va zavodlar bunday masalalarni qanday hal qiladi?

Javob

Qisqa javob: Variantlar soni eksponensial yoki faktorial o'sadi, tezlik esa faqat chiziqli yaxshilanadi: kompyuter 1000 barobar tezlashsa, marshrut masalasida bor-yo'g'i 2–3 ta nuqta ko'proq qo'shish mumkin bo'ladi. Amaliyotda aniq eng yaxshi yechim o'rniga yetarlicha yaxshi yechim qidiriladi: evristikalar, taqribiy algoritmlar, maxsus solverlar va masala tuzilishidan foydalanish orqali.

1. Nega tezlik yordam bermaydi

Kompyuter tezligi	`n!` uchun vaqt chegarasi 1 soat bo'lsa, maksimal `n`
10⁷ variant/s	≈ 13
10¹⁰ variant/s (1000× tez)	≈ 16
10¹³ variant/s (1 mln × tez)	≈ 18

Har qo'shimcha nuqta vaqtni n barobar oshiradi — tezlanish bir necha nuqtaga "yetadi".

2. NP-qiyinlik (qisqacha)

P — polinomial vaqtda yechiladigan masalalar (saralash, eng qisqa yo'l grafda)
NP — yechimni polinomial vaqtda tekshirish mumkin
NP-qiyin — barcha NP masalalar unga keltiriladi; hozircha ular uchun polinomial algoritm ma'lum emas
"P = NP?" — informatikaning eng mashhur ochiq savoli

Marshrut (TSP), qopdagi yuklar (knapsack), jadval tuzish, qamrov (set cover — Misol 4) — hammasi NP-qiyin.

3. Amaliyotda qanday hal qilinadi

Usul	G'oya	Misol
Dinamik dasturlash	Qism masalalar natijasini saqlash	Knapsack — psevdopolinomial; TSP — Held–Karp `O(n² 2ⁿ)`
Tarmoq va chegara (branch and bound)	Istiqbolsiz tarmoqlarni kesish	Misol 4 dagi kesishning kuchli varianti
Butun sonli dasturlash (MILP)	Masalani tenglamalar tizimiga aylantirish	Aviakompaniya ekipaj jadvali
Evristikalar	Tez, yaxshi, kafolatsiz	Eng yaqin qo'shni, 2-opt
Metaevristikalar	Lokal minimumdan chiqish	Simulyatsion otjig, genetik algoritmlar, tabu qidiruv
Taqribiy algoritmlar	Kafolatlangan sifat chegarasi	Set cover uchun ochko'z — `ln n` barobardan yomon emas
Masala tuzilishi	Real ma'lumotda qo'shimcha xususiyatlar	Yo'llar tarmog'i geometriyasi

4. Sanoat vositalari

Google OR-Tools — marshrut, jadval, knapsack, MILP
Gurobi, CPLEX, HiGHS — MILP solverlar
Concorde — TSP uchun: o'n minglab shaharli masalalarni aniq yechgan

5. Muhandislik xulosasi

Masalani tanib oling: "hamma variantni sinash" — ogohlantiruvchi belgi
Avval sanang (math.comb, math.factorial)
Kichik n — to'liq qidiruv (to'g'ri javob va test uchun etalon)
Katta n — evristika yoki solver; natijani kichik n da to'liq qidiruv bilan solishtiring
Biznesga "eng yaxshi" emas, "vaqtida va yetarlicha yaxshi" yechim kerak

Nimani mustahkamlaydi: 2.1–2.6-bo'limlar.

Xulosa

Bu darsda kombinatorik iteratorlarni va variantlar sonining portlovchi o'sishini o'rgandik.

Eng muhim uch fikr:

To'g'ri funksiyani tanlash — ikki savol. Tartib muhimmi va takrorlash mumkinmi? product — ikkalasi ham (n^k, ichma-ich tsikllar o'rnida), permutations — tartib muhim, takrorsiz, combinations — tartib muhim emas, combinations_with_replacement — takror bilan. Tanlov elementlarning pozitsiyasi bo'yicha: permutations("aab") 6 ta natija beradi, noyobi esa 3 ta.
Avval sanang, keyin yarating. math.comb, math.perm, math.factorial variantlar sonini bir zumda beradi. n! shunchalik tez o'sadiki, kichik n da o'lchangan tezlik 12 ta element uchun daqiqalarni, 15–20 uchun esa yillarni bashorat qiladi. Kesish (arzon tekshiruv avval), simmetriyani yo'qotish va chegarada algoritmni almashtirish — asosiy vositalar.
Dangasalikning chegarasi. Kombinatorik funksiyalar natijani bittadan beradi — next(permutations(range(20))) darhol ishlaydi. Lekin kirishni oldindan to'liq o'qiydi: cheksiz iterator berilsa osilib qoladi, katta generator esa xotiraga tushadi. Jamoa tanlash misolida esa ochko'z usul bir zumda ishladi, lekin eng arzon jamoani topmadi — tezlik va aniqlik orasidagi kelishuv.

Keyingi darsda functools moduliga o'tamiz: partial, reduce, lru_cache va cache, wraps, singledispatch, cached_property.

Ulashish:Telegram'da

Izohlar (0)

Izoh yozish uchun kiring.

Hozircha izoh yo'q. Birinchi bo'ling!

15.9-dars: itertools: kombinatorika

1. Kirish va motivatsiya

2. Nazariya — chuqur tushuntirish

2.1. To'rt funksiya

2.2. Sanash — yaratmasdan

2.3. Chegara holatlar va natija tartibi

2.4. Dangasalik chegaralari

2.5. Kombinatorik portlash

2.6. Keng tarqalgan andozalar

3. Tez ma'lumotnoma

4. Batafsil misollar

Misol 1 — To'rt funksiya va formulalar

Misol 2 — Portlovchi o'sish va dangasalik chegaralari

Misol 3 — Amaliy andozalar

Misol 4 — Amaliy: loyiha jamoasini tanlash

5. To'g'ri va noto'g'ri tushunishlar

6. Keng tarqalgan xatolar va yechimlari

7. Integratsiya — bu bilim qayerda kerak bo'ladi

8. Eng yaxshi amaliyotlar

9. Amaliy topshiriq

Xulosa

Izohlar (0)

15.9-dars: `itertools`: kombinatorika