[Delphi] lexicographic order

Nekateri jeziki to znajo že s priloženimi knjižnivami, ali so prepočasni?

Zdravo!

Thomas ne vem kaj točno misliš s tem "Prevedi v niz, posortaj ga in potem nazaj v string".

Owca trenutno delam v Delphi-ju 6 pa nisem zasledil, da bi zmogel lexicographic order. Bom še malo bolj povrtal v Delphi in če zmore bo vrejetno kar ok (takšni implementirani algoritmi ponavadi niso čisto trivialni).

LP

Zdravo!

To je že res o tem ni dvoma. Ampak to ni leksiografsko urejen niz, ki ga jaz želim. Če si pogledal moj primer

niz "210054" je leksiografsko urejen : "005421". Če pa bi uporabil navaden sort bi dobil "001245". torej določen niz moram s shiftiranjem spremeniti v niz, ki je leksiografsko najmanjši.

Takšan trivialna funkcija že naredi prav, ampak je časovno zelo potratna.

function lex_sort(s:string):string;
var x,y:integer;
min,hr1,hr2,st:string;
begin
//dolžina niza
x:=length(s);
min:=s;
for y:=1 to (x-1) do
begin
//šiftam za y okoli
hr1:=copy(s,x-y+1,y);
hr2:=copy(s,1,x-y);
st:=hr1+hr2;
//če je novo nastali string manjši od min
if (st (manjše) min) then min:=st;
end;
result:=min;
end;


Zanima me, če kdo pozna kakšno hitrejšo funkcijo (ki naredi enako), saj bom ta del kode izvajal relativno pogosto.

Hvala za pomoč.
LP

OK!

Ne vem, če se razumema prav.

Če bi uporabil navaden sort (quick, bubble,...) ne bi dobil željenega rezultata. Zato takšno urejanje odpade.

Zgoraj napisana fukcija ne dela tega, ker vse skupaj shiftira in preglejuje ali dobljeni string leksiografsko najmanjši glede na prejšnje. Fukcija je trivialna in zato zelo počasna.

Ne vem pa kaj misliš, "da za primerjanje uporabiš leksikografsko relacijo urejenosti".

LP

OK!

Nisma se zaštekala. Verjetno sem slabo opisal problem (moja slaba lastnost).

Jaz ne urejam več nizov med sabo, ampak želim en niz urediti tako, da ga zapišem kot leksiografsko najmanjši niz. Torej niz s šiftanjem obračam ("fghjk" - shift za 1 dobim - "ghjkf") tako dolgo dokler ne dobim leksiografsko najmanjši niz.

To tudi dela tista funkcija. Hočem ugotoviti ali obstaja hitrejša funkcija, ki bi mi opravila enako.

LP

Nisem glih siguren, da ti mene štekaš.


Črk ne morem premetavati lahko jih le šiftiram (ampak vse skupaj). Torej ne morem narediti iz "adaabbbce" = "aaabbbcde" ampak lahko ta niz preoblikujem le tako, da dobim nize "daabbbcea", "aabbbcead", "abbbceada","bbbceadaa", "bbceadaab", "bceadaabb", "ceadaabbb", "eadaabbbc".

Iz teh pa izberem leksiografsko najmanjšega.

LP

niz "210054" je leksiografsko MINIMALEN niz : "005421"
oz.
niz "dgber" je leksiografsko MINIMALEN niz : "berdg"

Moja napaka v napisu!

Hočeš reči, da imaš neko posebno dodatno omejitev in izmed cikličnih permutacij danega niza iščeš leksikografsko najmanjšega? Tiste ciklične permutacije so precej pomemben podatek in bi si zaslužil omembo že v prvem odgovoru.

Sam algoritem boš težko kaj izboljšal, izboljšaš pa lahko, kako je napisano.

Kot prvo, jaz ne bi uporabljal funkcije copy(), ampak bi raje naredil prostor za še enkrat daljši niz
ter potem prvo črko metal na konec stringa, v eni spremenljivki pa bi spremljal, katera je dejansko prva črka.

Druga ključna funkcija pa je leksiografsko primerjanje dveh stringov, ki mora takoj ko najde prvi večji znak,
vrniti rezultat (da ne boš slučajno gledal cel string do konca)

Sam bi pustil niz kot je in samo preračunaval kazalec na prvi element. Generiranje vseh cikličnih permutacij je tako O(n) problem in se poslužil tega kar svetuje Gundolf.