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 }
}
}