[solved] halmazfelsorolás

Algoritmusok

Ma pistike-gányolás közben beleütköztem egy problémába, amit csak nagyon rondán tudtam megoldani. A probléma általánosítása a következő:

Legyen A egy véges, nemüres halmaz, melynek bármely két eleme összemérhető. Soroljuk fel ennek a halmaznak az elemeit az összes lehetséges módon; éspedig úgy, hogy minden felsorolásban minden elem részt vegyen.

Intuitíve érzem, hogy erre létezik valami igazán egyszerű algoritmus, de sehogysem tudom megtalálni. Elővettem már a faktoriális definícióját, nézegettem az elemszám oszthatóságait, meg mindent, de hiányzik az "isteni" szikra. Azt szeretném kérni, hogy NE oldjátok meg helyettem a feladatot, csak adjatok valami ötletet, ami a lehető legelegánsabb megoldás első lépésére vezet rá. Köszönöm!

-------------------------------

A megoldás: rekurzió, ahogyan az első válaszban le van írva. Annyira végtelenül egyszerű, hogy talán pont emiatt nem is gondoltam rá.

  • 5231 megtekintés

( SzBlackY | 2013. 04. 22., h – 21:13 )

A triviális megoldás egy rekurzív algoritmus: egy N elemű halmaz összes lehetséges variációja az N elem és mindegyik elemehez a megfelelő N-1 elemű halmaz összes lehetséges variációja.

pl.: f({1,2,3}={[1, f({2,3})], [2, f({1,3})], [3, f({1,2})]}={[1, 2, f({3})], [1, 3, f({2})], [2, 1, f({3}], [2, 3, f({1})], [3, 1, f({2})], [3, 2, f({1})]}={[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}

BlackY

( joco01 v | 2013. 04. 22., h – 21:18 )

A kulcsszó: permutáció. Van rá ezer meg egy algoritmus, biztos találsz pszeudokóddal együtt, sőt, tetszőleges programnyelvben előre megírva.

--

( vol4 | 2013. 04. 22., h – 21:46 )

Legyen A egy véges, nemüres halmaz, melynek bármely két eleme összemérhető. Soroljuk fel ennek a halmaznak az elemeit az összes lehetséges módon; éspedig úgy, hogy minden felsorolásban minden elem részt vegyen.

Mondjuk tényleg eléggé sikerült elbonyolítanod a permutáció fogalmát (tizedikes - max. tizenegyedikes - gimis anyag)... Azt nem tudom, ebben a kontextusban mit akar jelenteni az, hogy bármely két eleme összemérhető, de szerintem te sem... :)

Nem értesz. Tudom, mi az a permutáció, csak erre a feladatra nem sikerült _egyszerű_ algoritmust készítenem. (ergo nagyon csúnyán oldottam meg a speciális feladatot, ami előkerült)

Összemérhetőség: vegyünk egy halmazt, aminek az elemei a következők: 1, 2, 3, 4, bálna. Tessék particionálni aszerint, hogy melyik az, amelyiknél bármelyik elem kisebb vagy egyenlő. :) (ez a példa így persze nem precíz)

Valahogyan így kellett volna kezdened: Legyen A egy nemüres halmaz, 'a' és 'b' pedig eleme A-nak. Azt mondjuk, hogy 'a' összemérhető 'b'-vel, ha ...

A pontozott részt természetesen neked kell megmondanod. Gyanítom, hogy valami új, a matematikában eddig nem használt fogalmat kellene alkotnod (halmaz elemeinek összemérhetősége), de igazából nem, mert te a rendezésre gondolsz.