Urejanje množic

[Kroko]

Imam seznam množic. Nekatere od teh množic vsebujejo podmnožice (ki so tudi na na tem seznamu).
Imam funkcijo, ki preveri, če je množica podmnožica (Contains).
Rad bi množicam nastavil njihovega direktnega starša (Parent).

Se pravi, če je situacija taka:
A
|--B
|----C
|--D
|----E

bi rad dobil rezultat:
A.Parent = null
B.Parent = A
C.Parent = B
D.Parent = A
E.Parent = D

funkcija "Contains" dela takole:
A.Contains(B) = true
A.Contains(C) = true
B.Contains(A) = false
...
se pravi vrne "true" tudi za podmnožice, ki niso direktno njene ampak je še ena vmes.

Potrebujem čimhitrejši algoritem in prosim za pomoč.

[GJ]

Ne vem kakšne variable so A,B... ampak recimo da so to kazalci (lahko je tudi index, ampak je počasnejši) na tvoj node oziroma množico.

Vsak node mora vsebovati kazalec na starša (parent).
Potem le v zanki gledaš parente in sub-parente od nekega node-a do null in jih vmes primerjaš z iskanim parentom, če sta enaka vrneš true.
Najhitreje je, če gedaš nazaj od sub-node-a in ne od glavnega node-a naprej!

[mucek]

Ne vem odgovora, ampak pred parlamentom so nazadnje za urejanje množic uporabili vodni top ...

[blasny]

Najhitrejsi algoritem je odvisen od tega kako in kje so shranjeni podatki. V kaksni podatkovni strukturi.
Tudi nisi nic napisal, kako je implementirana funkcija Contains, ali pa vsaj kaksna je njena zahtevnost O(n).

[Kroko]

Imam std::vector v katerem so objekti.
Se pravi, da je lahko gremo čez cel vektor in vsak objekt primerjamo z vsemi (se pravi spet gremo čez cel cel vektor).
Potem moramo samo še poštudirati, kako nastavljati parenta, da se bo nastavil samo direkten starš, ne pa tudi dedi in pradedi.

[blasny]

Torej imas vector mnozic? Kako je implementiran Contains?

Ce je operacija iskanja parentov tako pomembna, bi lahko imel mnozice ze shranjene v tree-ju, namesto v vectorju?

[Kroko]

bool Contains(const Obj& set, const Obj& subset);

Takole lahko začnem ampak to ni to:

Koda: Izberi vse

std::vector<Obj> list = GetList();

for (size_t i = 0; i< list.size(); i++)
{
  const Obj& test = list[i];
 
  for (size_t j = 0; j< list.size(); j++)
  {
    if (j == i) continue;
   
   if (Contains(test, list[j]))
     list[j].Parent = i;
  }
}


Nimam tree-ja, dobim list. Če bi imel tree bi bilo trivialno. Lahko bi tree zgradil vendar ga ne potrebujem.
Dejansko niti Parentov ne potrebujem - potrebujem samo globino. Na primer:
A = 0
B = 1
C = 2
D = 1
E = 2

[blasny]

Jao, jao, kaksna struktura. Ampak zanimiva naloga.
Tako kot imas zdaj, ti ne bo delalo. Ne smes kar povozit parent, ker ti Contains ne pove ali je to stars, pra-stars ali pra-pra-stars. You get the point.

Dvojnemu loop-u se tudi ne mores izognit, ker ti struktura nic ne pove o starsih in otrocih. In moras to sele zvedeti, tako da klices Contains.
Vsaj kolikor razumem, je to edina operacija, ki jo imas na voljo.

Ce parenta ne potrebujes, potem ga ne rabis shranjevat. Raje povecuj stevilo parentov == kolikokrat ti Contains(text, X) vrne true.

To je kar globina drevesa. Seveda pri predpostavki, da nimas ciklov. In pri predpostavki, da ima vsak objekt samo enega parenta.

[blasny]

Ce ves, da so objekti v listi urejeni lahko optimiziras drugo zanko.
Pod urejeni pomeni: da je parent objekta vedno za objektom, ali pa vedno pred objektom.
Ce niso urejeni, potem moras imeti obe zanki taki kot ju imas zdaj.

[Kroko]

... Raje povecuj stevilo parentov ...

Saj sem vedel, da je preprosta rešitev.

Sedaj so "luknje" pravilno najdene.

Clipboard01.png