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ó:
import java.util.LinkedHashSet;

/**
 * Generates all K size subsets of a given set. Returns with N!/K!(N-K)! combinations,
 * where K is the size of the combinations and N is the size of the base set. It
 * uses LinkedHashSet to keep the element order.
 *
 * @author JUZRAAI
 */
public class CombinationGenerator<T> {

    private LinkedHashSet<LinkedHashSet<T>> combinations = new LinkedHashSet<LinkedHashSet<T>>();

    /**
     * Generates all K size subset of the given set.
     * @param base The base set.
     * @param combinationSize The size of the combinations to be generated.
     */
    public CombinationGenerator(LinkedHashSet<T> base, int combinationSize) {
        gen(base, combinationSize);
    }

    private void gen(LinkedHashSet<T> base, int combinationSize) {
        if (base.size() < combinationSize) {
            return;
        }

        for (T item : base) {
            LinkedHashSet<T> subbase = (LinkedHashSet<T>) base.clone();
            subbase.remove(item);
            if (subbase.size() == combinationSize) {
                combinations.add(subbase);
            } else {
                gen(subbase, combinationSize);
            }
        }
    }

    public LinkedHashSet<LinkedHashSet<T>> getCombinations() {
        return combinations;
    }
}

Azért a LinkedHashSet implementációt választottam, mert az megtartja a sorrendet, és ez hasznos a progim szempontjából, amiben használni akarom.

2 megjegyzés:

auctorX írta...

Szia!

Nagyon tetszik a blogod ma találtam rá, iszonyat jó dolgokat írsz. Én nemrég kezdtem el foglalkozni a Javával és egyben a programozással sajna elég későn. De a lényeg a lényeg azt hiszem a blogod kész kincsesbánya számomra. :) Igazán örültem :D

juzraai írta...

Szia!

Köszi, én pedig örülök a pozitív visszajelzésnek. :)