Valaki tud tenni valamit?

Először egy egyszerűbb feladatot oldanék meg:

Először megengedem, hogy feltételezzük:

A két tömb elemei mind különböznek:

* az egyes tömbök külön-külön is különböző elemekből állnak (tkp. afféle halmazokként kezelhetők)

* meg a két tömb ,,egymástól'' is ,,idegen'', diszjunkt, nincs közös elemük.

Ez persze egyszerűbb feladat, mint az eredeti, hiszen feltételezzük, hogy a felhasználó ,,jóindulatúan'' ,,szép'' tömböket ad meg. De ha ez az egyszerűsített feladat már megvan, akkor az eredeti feladatot is könnyű megcsinálni: valamiféle előszűréssel, a tömbök ,,előzetes javításával'' ,,előkészítjük'' a tömböket, ,,kiszűrjük a felhasználó rosszindulatát'', és utána már az egyszerűsített megoldást nyugodtan ráereszthetjük a ,,kigyomlált'' tömbökre.

Most meg nézzük, mi is lenne az egyszerűsített megoldás (tehát ahol feltételezzük, hogy ,,jóindulatú' tömbadatok állnak rendelkezésünkre).

Én kettős, egymásba ágyazott ciklusként képzelem el. De még mielőtt az algoritmusról beszélnénk, nézzük meg, kell-e valami ideiglenes tárolókról, afféle pufferekről gondoskodni.

Globális változók:

int a[] = {1, 2, ... többi tömbadat} /* Az `a' adattömb */

int a_buffer[3]; /* Buffer majd minden egyes a-beli (3-elemű) variáció ideiglenes tárolására */

int b[] = {6, 7, ... többi tömbadat} /* A `b' adattömb */

int b_buffer[1]; /* Buffer majd minden egyes b-beli (1-elemű) variáció ideiglenes tárolására */

/* tkp. ez felesleges, egyelemű tömb esetén egyszerűbb helyette egy int b_item, hisz az 1-elemű variáció tkp csak annyit jelent, hogy a b-nek elég egyszerűen egyenként sorravenni az elemeit */

No a globális változók, bementi adatok, pufferek megvoltak, jöhet az algoritmus.

Én kettős, egymásba ágyazott ciklusként képzelem el. A külső ciklus kissé nehéz lesz, de egyelőre ezzel ne foglalkozzunk. Egyelőre élőszóban írom le, később törődjünk csak azzal, hogy ez a külső ciklus is valójában önmagában is három kis ciklusból fog állni. Ezt egy ideig ne nézzük, képzeljünk el egyelőre egy ,,fejlett'' ciklusutasítást, amivel ,,variációkon'' lehet végigmenni.

Szóval az algoritmus:

Külső ciklus: végigmegyünk az a tömb összes 3 lehetséges 3-elemű variációján. A külső ciklus minden egyes lépése egy-egy ilyen variációt állít elő. Az egyes variánsokat az `a_buffer' 3-elemű tömbbe (bufferbe) tesszük le tesszük le az épp aktuális cikluslépés erejéig. Ahogy mondtam, a megvalósítási részletekkel most ne torődjünk egyelőre.

Belső ciklus: végigmegyünk a `b' tömb összes lehetséges 1-elemű variációján (a megfogalmazás mesterként, tkp. egyszerűen sorra vesszük a `b' tömb elemeit). Az épp aktuális elemet a `b_item' globális változóba (vagy a `b_buffer' 1-elemű tömbbe) tesszük le az épp aktuális cikluslépés erejéig

Belső ciklus magva: `a_buffer' kiírása, melléírva `b_buffer' kiírása, és persze sortörés.

Belső ciklus vége

Külső ciklus vége.

Nohát én így képzeltem el a programot.

Tulajdonképpen sem az alapfeladatban sem `b_buffer' globális tömbre, sem a b_item változóra nincs szükség, hisz a belső ciklus egyszerűen csak végigveszi a b elemeit, ehhez elég egy sima index ciklusváltozó is. Azért írok mindvégig b_buffer tömbről, mert hátha később úgy lesz módosítva a feladat, hogy mondjuk a második tömbből is mondjuk valahányelemű variációkat kell venni.

- - - - - - -

Most hogy az áttekintés így megvan, már törődhetünk a külső ciklus megvalósításának részleteivel. Ugye ez a bizonyos külső ciklus a nehéz: ennek azt kéne nyújtania, hogy hogyan is lehet pl. egy húszelemű a-tömb összes lehetséges 3-elemű variációját előállítani, úgy, hogy a ciklus lépésenként egy-egy variációt tegyen le ideiglenesen az `a_buffer'-be.

Ez a részfeladat önmagában sem triviális, de egyelőre használjuk fel a könnyítést, amit a legelején említettem: egyelőre tegyük fel, hogy a felhasználó jóindulatú, és az a tömb csupa különböző elemmel van feltöltve.

Három indexváltozóval dolgoznám.

Az elsőt legelőre tenném, a másodikat melléje, a harmadikat pedig végigléptetném a maradék tömbön. Aztán az első indexet békén hagyva, a második indexet eggyel odébb tenném, a harmadikat megint a második mellé, és innen kiindulva a harmadikat megint végigfuttatnám a harmadikat a maradék tömbön. Olyan az elő index, mint az óra kismutatója: egyelőre meg sem mozdul, a második index olyan mint a nagymutató: néha pöccen egyet, a harmadik index meg olyan mint a másodpercmutató: az az, ami szaladgál.

Ha a második és a harmadik index így ketten végül kimeríti a tömbből adódó lehetőséget, akkor az eddig mindvégig mozdulatlan első indexet eggyel arrébb tenném (,,kismutató pöccenése''), tkp. a tömb fejét levágnám, immár egy eggyel rövidebb tömböt képzelnék a tömb helyébe. A második és harmadik index meg az imént nagy nehezen megpöccentett első index mellől újra elkezdené pályafutását (második index az első utáni, a harmadik meg a második utáni helyről).

Ebből is lehet érzékelni, hogy az, amit mindvégig ,,külső ciklus'' néven említettem (3-elemű variációkon való végigmenés), szóval ez a bizonyos ,,külső ciklus'' önmagában is egy háromszoros ciklust jelent. Ebben a háromszoros ciklusban a három index úgy mozdul meg egymáshoz képest, mint az óra másodpercmutatója, nagymutatója, kismutatója. Vagy mint a benzinkút forgós számlálójának számkerekei. A különbség csak az, hogy az ,,indexmutatók'' sosincsenek azonos pozícióban: az ,átpöccenésekkor'' egymás **mellől** indulnak, nem **fedik** egymást.

Majdnem kész vagyunk, de tulajdonképpen csak a könyített feladat van meg, még át kell gondolni, hogy a felhasználó rosszindulata esetén elő lehet-e valahogy szűrni a tömböket. Szóval amit a legeslegelején említettem.

Tkp. a pufferekre egyáltalán nincs szükség, hisz aaz adattömbök nem változnak, így mindvégig elég az indexek nyilvántartása.

A külső ciklus (ami az `a' tömb lehetséges 3-elemű variációin megy végig), az önmagában is egy 3-szoros egymásba ágyazott ciklusból áll. A nyilvántartott indexek: i, j, k (,,kismutató'', ,,nagymutató'', ,,másodpercmutató'')

Belső ciklus: ez egy sima for cilkus, egyszerűen végigmegy a b tömbe elemein. Ennek indexe legyen mondjuk m.

Legeslegbelső mag (a kiírás):

Kiíró utasítás: a[i],a[j], a[k], b[m], sortörés

Belső ciklus vége

Külső ciklus vége.

Így tkp, a bufferekre nincs semmi szükség.

-----

A külső ciklus, ami végigmegy az 'a' tömb 3-elemű variációin, azt igy képzelem

ciklus i index 0-tól 'a' tömb végéig

. , . , ciklus j index i+1 től a tömb végéig

. , . , . , . , ciklus k index j+1 től a tömb végéig

no ez az, amit külső ciklus néven emlegettem, ez kezelné az 'a' tömböt (a tömb 3-elemű variációin végimenés).

A ,,belső ciklus'' pedig még pluszban is ezen belül lenne, és persze ez meg a 'b' tömb "egyelemű variációin" menne végig (vagyis egész egyszerűen csak b tömb elemein):

. , . , . , . , , . , ciklus m index 0-tól b tömb végéig

No és még ennek magjában lenne az a bizonyos legeslegbelső mag, a kiíró rész, amit említettem:

. , . , . , . , , . , . , . , Kiíró utasítás: a[i],a[j], a[k], b[m], sortörés

A tömbök ,,előszűrését'' meg egyelőre így képzelem:

int a_tomb[] = {felhasználó adatai};

int b_tomb[] = {felhasználó adatai};

int javitott_a_tomb = `a_tomb'-ből kiszűrjük az ismétlődőket;

int javitott_b_tomb = `b_tomb'-ből kiszűrjük az ismétlődőket;

és innentől már az előbb megadott dolgok jönnének, amik persze már a javított tömbváltozatokkal dogoznának.

Még hátra van az a rosszindulatú eset, amikor az 'a' tömb, és a 'b' tömb ugyan külön-külön jók lennének, de a két tömb között vannak átfedések.

Pl.

a = {1, 2, 3, 4}

b = {1}

A példából is látszik, hogy itt nem segít az előszűrés. Ha egyszerűen kiszedjük a b-ből az 1.est (azon az alapon, hogy az megvan a-ban), akkor a feladat megoldhatatlanná válna. Pedig nyilvánvalóan megoldható: 2341.

Tehát ha a két tömb között vannak átfedések, ott nem előszűréssel kell segíteni a dolgon, hanem pl. úgy, hogy a legeslegbelső ciklusmag

. , . , . , . , , . , . , . , Kiíró utasítás: a[i],a[j], a[k], b[m], sortörés

ez figyelné, hogy a négy kiírt szám közül az utolsó nincs-e meg az első három között, és ha igen, akkor egy continue utasítással kihagyná azt a lépést:

. , . if (b[m] == a[i] || b[m] == a[j] || b[m] == a[k])

. , . . , . continue;

. , . else

. , . . , . printf("%d, %d", %d, %d\n", a[i], a[j], a[k], b[m]);

A ,,variáció'' szó picit zavaró hogy ezt használtam, tkp. itt nem is variációk, hanem (ismétlés nélküli) **kombinációk** leszámlálásáról van szó. Szóval az A tömb feldogozásával kapcsolatos részek (,,külső ciklus'') helyes matematikai megfogalmazása a következő(szerintem, egyelőre):

Van egy A halmaz. Az A halmaznak képezzük az összes 3-ad osztályú ismétlés nélküli kombinációját.

[link]

Nincs ismétlés, és az elemek sorrendje nem számít. Az a-tömböt pedig halmaznak tekintjük, az ismétlődő elemeket nem vesszük figyelembe (pl előzetesen kiirtjuk a duplikátumokat).

Arról pedig, hogy az A kombinációinak felsorolásáról gondoskodó programrész által kiadogatott esetek során az elemek sorrendje tényleg ne számítson, úgy gondoskodunk, hogy a három a-tömbindex mindvégig úgy mozog, hogy az i < j < k sorrend mindvégig fennálljon. Ez az, ami garantálja, hogy ne számítsunk kétszer olyan esetet, ahol csak a kiválasztott elemek sorrendjében lenne eltérés. Ha a három a-tömbindex mindig is csak i,j,k sorrendben állhat (persze nem feltétlen szomszédosan, de pl a j sose állhat az i előtt, sem a k a j előtt), szóval a három index mindig is csak i,j,k sorrendben állhat, akkor biztos nem fog bejönni a 537 mellé még a 753 is.