Ekvivalenciaosztályok megszámolása

Algoritmusok

Probléma egyszerünek hangzik:

Adott egy N-elemü halmaz (vektor). Hány különbözö eleme (komponense) van?

Ugye ha mind különbözik, akkor N. De általánosan nem mind különbözik - mondjuk legyen N=4, és a vektorom {1,2,1,3}-ekkor 3 egyenlöségi osztály van. Kérdés egy olyan algoritmus, amely:

1. megszámolja az osztályokat, legyen számuk K
2. nem elég, hogy megszámolja öket, de visszatér egy K-dimenziós tömbbel, melynek elemei az eredeti vektor egyes osztályokba tartozó komponenseiböl álló tömbök, tehát a példánál maradva K=3, és a visszatérö tömb {(1,3),2,4}.

  • 6888 megtekintés

Hát az adott problémára (amikor a tömbelem típusa egész szám) az egyik legegyszerűbb a következő.

Először is, a tömbelemet kibővíted egy második mezővel. Vagyis nem skalár lesz a tömbelem, hanem egy két mezővel rendelkező struct. Az első mező az eredeti érték, a második mező az eredeti pozíció a tömbben. Ennek a tárköltsége O(n).

A megadott példánál maradva 


{
  { 1, 1 },
  { 2, 2 },
  { 1, 3 },
  { 3, 4 }
}

Ezt a tömböt rendezed (pl. helyben), az első mező szerint, stabil rendezéssel. A stabil rendezés azt jelenti, hogy ha az eredeti értékek megegyeznek egy összehasonlításban, akkor a második komponens (ami egyedi, tehát sosem egyezik meg) dönt a sorrendről. Ez biztosítja, hogy két azonos kulcsú elem relatív sorrendje sosem változik meg. Példa: (1, 1) < (1, 3).

A rendezés műveleti költsége legyen O(n log(n)). Például létezik "in-place merge sort", ami garantáltan ekkora műveleti igénnyel rendelkezik, nincs extra tárigénye, stabil is ráadásul, csak talán kicsit bonyolultabb. Mindenesetre vagy a tárigénynek, vagy a műveleti igénynek engedhetsz rosszabbat. 


{
  { 1, 1 },
  { 1, 3 },
  { 2, 2 },
  { 3, 4 }
}

A rendezett tömbben az első mezőben az azonos értékek egymás mellé kerülnek, a második mező pedig az eredeti pozíciót őrzi. Azonos első mezőn belül szigorúan monoton növekvő a második mező (stabil volt a rendezés).

A rendezett tömbön sorban végigmész (O(n)), nézed, mikor változik az első mező értéke. Amikor változik, akkor kezdesz új osztályt. Ahányszor változik, annyi osztály van. Egy adott osztály elemeit (az eredeti pozíciókat) a kapcsolódó második mezők értéke adja meg.

Általánosabban megközelítve: arra van szükseged, hogy bármely eredeti elemből származtatni tudd a reprezentánst (az ekviv. osztály azon kitüntetett elemét, amely az osztály összes elemét reprezentálja). Például P szerinti maradékosztályoknál ez a származtatás a "X mod P", de lehet akármi más is (nem kell, hogy numerikus legyen).

Csinálsz egy asszociatív tömböt, amelynek a kulcsa a reprezentáns, értéktípusa pedig egy másik asszociatív tömb. Az utóbbi asszociatív tömb kulcsa az eredeti elem, értéke pedig egy pozíciólista.

Például legyen az eredeti lista {10, 7, 8, 7, 4, 2, 8, 3, 7, 2}, az osztályképző reláció pedig az "x kongruens y-nal, modulo 3". Ez ekvivalencia-reláció: reflexív, szimmetrikus, tranzitív; a reprezentáns pedig legyen bármely x-hez az az y, amely kielégíti a kongruenciát x-szel, valamint [0..2]-be esik. Ekkor a végleges adatszerkezet így fog kinézni: 


{
  0 => {
         3 => { 7 } /* 3 kongr. 0 mod 3; 3 pozíciói: 7 */
       },
  1 => { 
         10 => { 0 },       /* 10 kongr. 1 mod 3; 10 pozíciói: 0 */
          7 => { 1, 3, 8 }, /*  7 kongr. 1 mod 3; 7 pozíciói: 1, 3, 8 */
          4 => { 4 }        /*  4 kongr. 1 mod 3; 4 pozíciói: 4 */
       },
  2 => {
         8 => { 2, 6 }, /* stb */
         2 => { 5, 9 }
       }
}

Szerintem egy kicsit túlbonyolítod a problémát, de ami szemet szúrt igazán, az ez: az in-place merge sort műveleti igénye az bizony O(n*(log n)^2).
A tárigénye tényleg 1 és stabil, de ennek ez az ára.

Ezt ajánlom mert jól jöhet még:
http://en.wikipedia.org/wiki/Sorting_algorithm

az in-place merge sort műveleti igénye az bizony O(n*(log n)^2)

Szopacs. Természetesen kommentelés előtt belelestem a wikipedia-ba, azonban félreolvastam ezt a mondatot:

Stable sorting in-place is possible but is more complicated, and usually a bit slower, even if the algorithm also runs in O(n log n) time (Katajainen, Pasanen & Teuhola 1996).

("akkor is, ha")

így:

Stable sorting in-place is possible but is more complicated, and usually a bit slower, even though the algorithm also runs in O(n log n) [...]

("bár" / "annak ellenére, hogy")

kínos...

( petrospolinakis | 2013. 01. 29., k – 00:20 )

Odáig eljutottam, hogy nyilván az N-elemü vektor minden elemét mindegyikkel összevetni N-alatt a 2-féleképpen lehet, de ennyi különbözö érték tutira nincs, mert ez több, mint N. Próbálom úgy, hogy van N csúcsom, meg kell számolni, hány független fürt van.

( NagyZ v | 2013. 01. 29., k – 00:40 )

ekvivalenciaosztalyokra bontashoz kene egy operator is azon a szerencsetlen halmazon... :)

ha az {1,2,3,1} -en az operator az, hogy "megegyeznek", akkor {1, 1}, {2}, {3} -ra lehet szetvagni, de altalanossagban nincs ertelme.

az (1,3),2,4 -et nem is ertem, honnan szedted.

( nullzero | 2013. 01. 29., k – 00:49 )

Hát én mondjuk rendezném őket kapásból (n*log n lépés), rendezett tömbön meg már jóval egyszerűbb dolgozni.
1. Az egyenlőek egymás mellé kerülnek, K tehát egyszerűen meghatározható.
2. az eredeti helyüket rendezés előtt eltárolod minden elem mellé, így a kívánt tömböd is kijöhet (ha jól értettem, ez kell)
Ez így összesen is n*log n lépés.

Ha nincs rendezés definiálva az elemekre, akkor O(n^2) időben lehet megoldani:
egy ciklussal végigmész az elemeken, majd mindegyik elemre meghívsz egy "Elhelyez(elem, index)" eljárást, amely egy listák-listája adatstruktúrában megkeresi, hogy az adott elemnek létezik-e már listája (ekvivalenciaosztálya) - ez egy O(n) művelet, hiszen csak egyezőséget vizsgálhatsz, ha létezik, akkor a megfelelő lista végére szúrja az elemet az index-szel együtt, amúgy pedig új listát hoz létre.

Ez így összesen O(n^2) művelet.

Attól, hogy egy halmazra létezik definiált ekvivalenciareláció ( egy reflexív, tranzitív, szimmetrikus reláció), még nem biztos, hogy a halmazra létezik definiált rendezési reláció (egy reflexív, tranzitív, antiszimmetrikus reláció).

Jól ismert példa, hogy a komplex számokra nem létezik olyan rendezési reláció, amely művelettartó lenne a komplexeknél szokásosan definiált összeadás és szorzás műveletekre.

Nem érted a dolgot.
Nem kell névvel vagy azonosítóval rendelkeznie két halmazbeli elemnek.
Gondolj arra, hogy olyan algoritmust kell írnod, ahol két halmazbeli elemhez csak egy equals(a,b) eljárásod adott, de nem tudod annak belső működését, azaz csak az ekvivalenciareláció ismert, de az már nem, hogy miként van definiálva (hiszen általánosan működő algoritmust keresünk).
És általános esetben az ekvivalenciarelációnak semmi köze nevekhez meg azonosítókhoz, csak egy ekvivalenciareláció.

A jelegnlegi esetben természetesen NEM kell osztani meg szorozni, csak egy példát hoztam fel arra, hogy vannak olyan halmazok, amikre nem definiálnak rendezési relációt, de ekvivalenciarelációt igen.

( persicsb | 2013. 01. 29., k – 00:55 )

Halmazod, vagy vektorod van? Azaz sorszámozott vagy nem sorszámozott ez a kollekció?
Ha nem sorszámozott, akkor a második pontban leírt dolog nem valósítható meg, hiszen az impliciten feltételezi, hogy léteznek sorszámok.

Az első problémára:
mekkora futásidőben és tárterülettel kellene megoldani?
Mert egy lehetséges megoldás: O(n*log n) lépésben rendezet a vektort tetszőleges módon, majd O(n) lépésben meghatározod a komponensek számát: 


K = 0;
Temp = A[0];
Ciklus I=1-től N-1-ig // feltesszük, hogy 0 és N-1 között léteznek indexek
Ha A[I] != Temp Akkor K = K + 1; Temp = A[I];
Ciklus Vége

Ha ezután meg akarod határozni a komponensek helyét is, akkor kell egy N*K méretű bináris táblázat, ahol pont akkor szerepel Igaz érték a táblázatban, ha a vektor N-ik eleme része a K-ik komponensnek.
Ezt pedig szintúgy triviális feltölteni, a rendezés során ugyanis felépíthetsz egy olyan leképezést (map-et), ami megmondja, hogy a tetszőleges n szám a rendezés előtt hányadik helyen állt a tömbben. Ezután a táblázat felépítése csak egy lookup művelet, a komponensek szerinti listázás pedig ennek a táblázatnak a sorok szerinti kiolvasása.

Szerk. nullzero megoldása jobb.

( Aadaam v | 2013. 01. 29., k – 03:01 )

esetleg hash-sel?

fogsz egy hash-t, edesmindegy, mi, mondjuk legyen egy HashMap.

HashMap<elem,array*> map = new HashMap<elem,array*>;
int osztalyok = 0;
for (index:elem in vector):
    if map.hasElem(elem):
        map[elem].push(index)
    else:
        map[elem] = new array<int>(index);
        osztalyok+=1;
return (osztalyok, map)

Ez egy gyakorlati megvalositas, igazabol te egy - optimalis esetben - n db. ordo(1)-es kulcskeresest vegzel el, ill. k. db. beillesztest (most ennek a koltsege azert fugg k es a hashtabla meretenek viszonyatol)

Lehet,hogy ennel van gyorsabb, sokminden fugg a konkret adat kardinalitasatol (azaz k-tol, ill. annak nagysagrendjetol), a hash algoritmustol, lehet, hogy egy masik indexelesi eljarast kell alkalmazni, de a rendezest en soknak erzem, remelem,annal azert ez gyorsabb realis esetekben.

Hashfüggvény természetesen mindig értelmezhető, de nem biztos, hogy konzisztens lesz az ekvivalenciarelációval. Nem véletlenül hívják fel a figyelmet Javasoknak, hogy a hashCode és equals metódusokat mindig egyszerre definiáld felül, ha a.equals(b), akkor a.hashCode() == b.hashCode() kell legyen (de ez fordítva nem igaz, előfordulhat, hogy !a.equals(b), de a.hashCode()==b.hashCode(), pont ez a hash ütközés).

Ahhoz, hogy ez működjön, kell lennie olyan hash implementációnak, ami konzisztens az equals-szal. Azonban a feladatban egyáltalán nincs erről szó, csak létezik a (sorszámozott) halmazon egy ekvivalenciareláció, többet nem tudunk, azaz azt sem tudjuk, hogy létezik-e equals-konzisztens hash, innentől kezdve HashMap nem használható.

Eloszor is a problema tudtommal nem elmeleti, a gyakorlatban ha mast nem, a sorositas (es a legtobb ertek egy gyakorlati vilagban sorosithato) konzisztens hash-t kepez az equals-szal, ill. egy gyakorlati hashmap eltarolja a kulcsot is, szoval nincs "a hashCode egyezik de az ertek nem, visszaadok neked egy hottmasik elemet" szituacio (hacsak szandekosan el nem b.sszuk, nyilvan)

" szoval nincs "a hashCode egyezik de az ertek nem"
Hat miert ne lenne ilyen? Ha nem lenne, akkor nem letezne a hash utkozes, es a hash szamitasnak se lenne ertelme.
Pont ez a lenyege a hashelesnek: egy nagyobb elemszamu halmazt lekepezunk egy kisebb elemszamu halmazra.

Szerk.
Másrészt a szerializácio nem hashfüggvény, mert a hashfüggvény pont attól hashfüggvény, hogy nem injekció, csak szürjekció. A szerializáció viszont injekció.

A return 0; valóban konzisztens az equals-szal: ha a.equals(b) akkor a.hashCode() == b.hashCode(). Ez egyértelmű, ha minden elemre ugyanaz a hashCode.

Azonban sokan rosszul implementálják a hashCode-ot (elfelejtik implementálni akkor, amikor implementálják az equals-t), ezért előfordulhat, hogy a.equals(b), de a.hashCode() != b.hashCode().
Ekkor mondjuk, hogy a hashCode nem konzisztens az equals-szal.

De beszéljen helyettem a java.lang.Object.hashCode() specifikációja:
"The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables."

Ez mind igaz, és tisztában vagyok velük (remélem :) ).

Én erre reagáltam:

"Ahhoz, hogy ez működjön, kell lennie olyan hash implementációnak, ami konzisztens az equals-szal."

Tehát azt írod (felhasználva az idézett definíciót), hogy kell egy h hashfüggvény, amire
a = b -> h(a) = h(b)

De ahhoz, hogy Aadaam megoldása működjön, olyan hashcode kellene, amire ez a nemszokványos feltétel is teljesül:

h(a) = h(b) -> a = b

Ez pedig nem következik abból, hogy h konzisztens az egyenlőséggel.

Igazad van, ez benéztem, és hülyeséget írtam.

Akkor lenne elég az equals-konzisztens hashfüggvény, ha a mapben nem elemeket, hanem hash-eket tárolna. Nem jó dolog reggel 8-kor pszeudokódot olvasni :)

Az már megint más kérdés, hogy szerintem Aadaam keverte a szóhasználatban a hash-t, a HashMapet és a hashfüggvényt.
Amire ő hash-ként gondolol, az egy kulcs-érték asszociatív tár, Java nyelvezetben Map, .Net nyelvezetben dictionary.
"fogsz egy hash-t, edesmindegy, mi, mondjuk legyen egy HashMap."

A HashMap csak egy ilyen lehetséges Map implementáció ofkorz, ami belül pont hashtáblákat használ.
És ahhoz, hogy a java.util.HashMap működjön, tényleg csak egy equals-konzisztens hashCode kell, más nem.

( oszkar v | 2013. 01. 29., k – 08:02 )

Csak a rend kedvéért (és egyáltalán nem lényeges, ne vegye senki kötekedésnek): a halmaz elemei definíció szerint különbözőek. Szóval ez lehet tömb, vektor, mátrix, miegymás, de halmazként csak N különböző eleme lehet.

( viraghj v | 2013. 01. 29., k – 11:07 )

Ha szabad csalni, a Maple-ben ez kb. ennyi :)

> L := [1, 3, -2, 3, 2, 5, 5]:
> EqClasses := {}:

> for elem in L do EqClasses := EqClasses union {{ListTools[SearchAll](elem, L)}} od:

> op(EqClasses);

{1}, {3}, {5}, {2, 4}, {6, 7}

( petrospolinakis | 2013. 01. 29., k – 13:14 )

Na, látom, sokaknak megtornáztattam az agyát! :) Én is felébredtem időközben, és a következőt sikerült megszülnöm (ez éppen MATLAB kód): 


function eqv=equivalence(A)

    eqv=size(A,2);                           %Alapból tekintsük úgy, hogy a vektor minden komponense független
    idx=1;                                   %azon elem indexe, amihez megnézem, hogy a többi egy osztályban van-e vele 
    flag(1:eqv)=false;                       %Ez a flag jelzi, hogy osztályoztunk-e már egy elemet
    i=1;                                     %futóindex
    while not(all(flag))                     %Addig csináljuk, amíg mindenkit leosztályozunk
        
        if(i>size(A,2))                      %Ha elérjük a vektor végét, mars vissza az elejére 
           i=1;                              %Először nézzük meg, hogy ki van az 1.elemmel egy osztályban (lehet, hogy csak önmaga),... 
           idx=idx+1;                        %majd a következővel, majd a következővel, sít.
        end

        if( not(flag(i)) && (A(idx)==A(i)) ) %Csak akkor nézünk valamit, ha még nincs osztályozva
                                             %Ha van egyezés, az osztályozva lesz
           if(idx~=i)                        %A független elemek számát csökkentjük, ha van vele egyenlő, ami nem önmaga
               eqv=eqv-1;
           end
           flag(i)=true;                     %Ha van egyezés, az osztályozva lesz -> flagjét bebillentjük, legközelebbi 
        end                                  %körben már őt nem vizsgáljuk, átugorjuk
        i=i+1;
        
    end
    
end