Kombinatorikai programot hogy oldanátok meg?

Mondjuk ha írsz egy programot, ami kigenerálja az összes számot, és csak a jókat írja ki (és számolja meg), azzal mi a baj?

Konkrétan nem kell hozzá érteni se a feladatot. (attól még jó, ha érted, de majd a program megszámolja helyetted)

Ez tipikusan olyan feladat amit nagyon sokféleképpen lehet megoldani. Én így kezdenék neki:

Tekintsünk el a számjegyek sorrendjétől, generáljuk számjegy halmazokat. Minden halmaz 5 elemű ami és ilyen formában írható fel:

{1, 2, x, y, z} ahol x=[3,7], y=[x+1,8], z=[y+1,9]

Ez 3 szimpla for ciklus és legeneráltuk az összes számjegy kombinációt (nincsenek duplák ha így adod meg).

Most nézzük a sorrendet:

Ahhoz hogy minden számjegyhalmazt minden sorrendbe felírjuk, csupán fel kell írnunk az összes permutációját. Permutációra van egy halom algoritmus.

A program ekkor így néz ki:

for x in 3..7

. for y in x+1..8

. . for z in y+1..9

. . . permutációk_kiírása(1, 2, x, y, z)

Most egy kis matek a lehetőségek számáról: az 1 és 2 fix, a maradék 3 helyre pedig kiválasztunk 7 számjegyből 3-at úgy hogy nincs ismétlődés és a sorrend nem számít. Ez ugyan az mint a lottó sorsolás, azaz egy mezei kombináció (7 alatt a 3). Majd ezt az 5 számot megpermutáljuk ami egy mezei permutáció (5!). Így a lehetőségek száma: (1 * 1 * C(7,3)) * P(5) = 7!/(3!*4!)*5! = 4200