2012. május 28., hétfő

Kombinációk generálása

Jelenleg egy olyan progin dolgozom, amiben szükség lenne arra, hogy megkapjam N darab szám összes K (0<K<N) számból álló kombinációját. Ilyen kombinációkból pontosan N!/K!(N-K)! darab van. De hogy is kéne ezeket meghatározni? Én a következőképp csinálnám:

Példaként az { 1, 2, 3, 4 } halmazból válasszuk ki a 2 elemű részhalmazokat!

Így gondolkodtam:

kiveszem: { 1 }, marad: { 2, 3, 4 }
    kiveszem: { 2 }, marad: { 3, 4 } --> KIMENET
    kiveszem: { 3 }, marad: { 2, 4 } --> KIMENET
    kiveszem: { 4 }, marad: { 2, 3 } --> KIMENET
kiveszem: { 2 }, marad: { 1, 3, 4 }
    ...

Vagyis algoritmikusan:

adott az alaphalmaz
az alaphalmaz minden E elemére {
    halmaz = alaphalmaz - E
    a halmaz minden F elemére {
        kombináció = halmaz - F
        kimenet << kombináció
    }
}

Viszont ez csak 2 elem kivonását végzi el, ha kisebb kombinációkra van
szükségünk, akkor több ciklus kell egybe ágyazva. Viszont a ciklusmagok
ugyanazt a feladatot végzik -> így megoldhatjuk rekurzióval a feladatot:

kombinációk(alaphalmaz, k) {
    az alaphalmaz minden E elemére {
        halmaz = alaphalmaz - E
        ha |halmaz| = k
            kimenet << halmaz
        különben
            kombinációk(halmaz, k)
    }
}

Ezzel az algoritmussal, - ha fent végigjátsszuk, láthatjuk, hogy - egy kombinációt többször is ki fog adni. Biztosan meg lehet oldani algoritmikusan, hogy ezt elkerüljük, ezen most nem gondolkodtam, de Java-ban erre egy egyszerű megoldás: a kombinációkat halmazban gyűjtjük. Java implementáció:

2012. május 21., hétfő

Osztott rendszerek vizsgához

Készítettem egy doksit az Osztott rendszerek vizsgához. Ez nem a diasorok teljes fordítása és nem is feltétlenül a teljes anyag. Elsősorban magamnak csináltam, a jegyzeteim és a diasorok alapján, de úgy gondoltam, közzé teszem, hátha valakinek hasznos lehet még. Ha a valakit érdekel, a mappámban elérhető: LINK. Jó készülést, sok sikert! :-)

Update 2012.05.21. @ 22:04
néhány elírás kijavítva, tételek vázlatosan is bekerültek, a doksi végére

Update 2012.05.22. @ 17:13
néhány elírás kijavítva, vázlat pofozgatva egy picit

Update 2012.06.11. @ 12:43
flat elnevezéseknél a finger tábla működése javítva, kiegészítve

2012. május 17., csütörtök

Online compiler

Most, mielőtt kiraktam az euklidészi algoritmust megvalósító Python szkriptemet, azért le akartam ellenőrizni, hogy jó-e. Mivel a gépemen most nincs Python telepítve, és lusta is vagyok feltenni, rákerestem online interpreterre, és lőn, ezt találtam:


Több, mint 40 programnyelvet ismer, beillesztesz egy kódot, ő meg lefordítja és futtatja szerveroldalon, és kiírja az output-ot. A fent említett progim tesztelésére nagyrészt jó volt, csak parancssori paramétereket nem lehet megadni neki. (Vagy legalábbis nem látom, hol lehetne.)

Bővített euklidészi algoritmus

Korábban volt egy "Diszkrét Matematika I. - II." című cikkem, melyet proginfes sorstársaimnak készítettem. Mivel az egy nagyon hosszú bejegyzés volt (meg munkás is, sok képet kéne feltölteni újra), úgy gondoltam, most szétdarabolom kisebb, elkülönülő bejegyzésekre.

Elsőként a Számelmélet témakörhöz szeretném hozzátenni a bővített euklidészi algoritmus általam írt Python implementációját.

Definíció


Meghatározza az a és b egész számok d legnagyobb közös osztóját, valamint az x és y egész számokat, melyekre d=ax+by teljesül. Az eljárás során végig axn+byn=rn, n=0,1...

Algoritmus

  1. Inicializálás:
    • x[0] := 1
    • y[0] := 0
    • r[0] := a
    • x[1] := 0
    • y[1] := 1
    • r[1] := b
    • n := 0
  2. Vége?
    • Ha r[n+1] = 0, akkor x := x[n], y := y[n], d:= r[n] és az eljárás véget ért
  3. Ciklus:
    • q[n+1] := r[n] div r[n+1]
    • r[n+2] := r[n] mod r[n+1]
    • x[n+2] := x[n] - x[n+1] * q[n+1]
    • y[n+2] := y[n] - y[n+1] * q[n+1]
    • n := n + 1
    • -> 2.
(A definíció és az algoritmus forrása a Járai féle Diszkrét Matematika könyv.)

Python implementáció

import sys

a, b = int(sys.argv[1]), int(sys.argv[2])
x = [ 1, 0 ]
y = [ 0, 1 ]
r = [ a, b ]
q = [ 0 ]
n = 0

while (r[n+1] != 0) :
    q.append(r[n] // r[n+1])
    r.append(r[n] % r[n+1])
    x.append(x[n] - x[n+1] * q[n+1])
    y.append(y[n] - y[n+1] * q[n+1])

    # egyszeru kiiras
    #print r[n], "=", r[n+1], "*", q[n+1], "+", r[n+2]

    # bovitett kiiras
    #print r[n+2], "\t", x[n+2], "\t", y[n+2], "\t",
    #    r[n+2], "=", a, "*", x[n+2], "+", b, "*",
    #    y[n+2]

    n += 1

x, y, d = x[n], y[n], r[n]

print "\n", d, "=", a, "*", x, "+", b, "*", y
A progi két parancssori paramétert vár: az a és b számokat.

2012. május 9., szerda

nanotime

Olykor szükségünk lehet arra, hogy megmérjük, mennyi ideig hajtódott végre egy függvényünk. Erre a System osztályban van 2 hasznos statikus metódus. Egyfelől van a currentTimeMillis(), ami milliszekundumban adja vissza az aktuális időt, illetve van a nanoTime(), ami viszont már nanoszekundumos pontossággal. Csak hogy átlássuk az SI mértékegység-rendszer releváns részét:

milli: 10-3
mikro: 10-6
nano:  10-9

Vagyis 1 nanoszekundum = 10-9 másodperc.

A mérési feladat elég szimpla:
long t = System.nanoTime();
valami();
t = System.nanoTime() - t;

És meg is kapjuk, hogy a függvény hány nanoszekundum alatt futott le. Ezzel csak az a baj, hogy ha kiíratunk egy ilyen számot önmagában, ránézésre nem egyszerű megmondani, hogy most ez hány másodperc vagy esetleg perc volt. Érdemes tehát kreálni egy függvényt, ami szépen megformázza ezt a long-ot, és kiköhög nekünk egy olvasható String-et. :-)

/**
 * Transforms a time in nanoseconsds to a readable text.
 * Output format: MM:SS.MS,mS'nS
 * @param time Time to format.
 * @param showMicro Include microseconds in the text?
 * @param showNano Include nanoseconds in the text?
 * @return The time as text.
 */
public static String formatNanoTime(long time,
                                    boolean showMicro,
                                    boolean showNano) {
    long nanosec = time % 1000;
    long microsec = (time / 1000) % 1000;
    long millisec = (time / 1000 / 1000) % 1000;
    long sec = (time / 1000 / 1000 / 1000) % 60;
    long min = (time / 1000 / 1000 / 1000 / 60);

    String r = lpad(Long.toString(min), 2, '0') + ":"
     + lpad(Long.toString(sec), 2, '0') + "."
     + lpad(Long.toString(millisec), 3, '0');
    if (showMicro) {
        r += "," + lpad(Long.toString(microsec), 3, '0');
    }
    if (showMicro && showNano) {
        r += "`" + lpad(Long.toString(nanosec), 3, '0');
    }
    return r;
}

Nem volt kis meló összerakni az osztásokat, maradékképzéseket... izzadtam vele egy ideig, de sikerült. :-)
Az lpad(String, int, char) függvényem annyit csinál, hogy jobbról kiegészíti a szöveget a megadott karakterrel, a megadott hosszúságra. Ezt nem illesztem be, 3 soros ujjgyakorlat.