Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Gleichmäßige Aufteilung von Texten in Kategorien


Flamefire - Do 14.02.13 16:17
Titel: Gleichmäßige Aufteilung von Texten in Kategorien
Ich habe eine Liste (Array) von Wörtern, die ich in Kategorien alphabetisch einsortieren will. In Kategorie 1 sollen z.b. Alle, die mit A-C anfangen. Kategorie 2 dann alle von D-G usw.
Jetzt die Frage: Wie kann ich diese möglichst optimal verteilen, so dass ich eine bestimmte Kategorieanzahl erhalte?

Bsp:
A, B, C, D, E
4 Kategorien:
1)A-A
2)B-B
3)C-C
4)D-E
-->In jeder Kategorie sind annähernd gleich viele Elemente.
Anmerkung: Kategorien sollen disjunkt sein. Also kann keine Kategorie mit einem Buchstaben aufhören, mit dem eine andere anfängt.

Versucht habe ich jetzt folgendes: AnzElProKat=AnzElGesammt/KatAnzahl
in einer for-schleife gehe ich die Elemente durch, und wenn bei einem Buchstabenwechsel die AnzElProKat überschritten wird, ziehe ich dort die Grenze.
Problem: In der ersten Kategorie gibt es AnzElProKat-1 Elemente mit gleichem Buchstaben --> Alle Elemente mit dem nächsten Buchstaben werden mit hinzugenommen --> Sehr ungleichmäßige Aufteilung da den anderen Kategorien natürlich dann die Elemente fehlen.

Hat da jemand eine Idee? Die Berechnung wird sehr häufig ausgeführt, also ist Geschwindigkeit wichtiger als eine optimale Lösung.


Gausi - Do 14.02.13 16:42

Die Frage ist ja immer nur: "Nehme ich den nächsten Buchstaben noch mit rein, oder nicht?"

Mögliche Lösungsskizze


Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
ges: Gesamtanzahl der Elemente
n: gewünschte Anzahl der Kategorien
ges/n = optimale Aufteilung (Anzahl Elemente pro Fach)

tmp: bisher abgefertigte Elemente, initial 0
for i = 1 to n do
begin
   Fülle Fach i, bis "tmp" größer wird als "i * ges/n" und bilde die Differenz
   Nehme letzten Buchstaben raus und bilde die Differenz zu "ges/n"

   Nutze die Variante, wo der Absolutbetrag von "tmp - (i * ges/n)" kleiner ist
end


Fülle die Fächer also nicht einzeln mit "ges/n", sondern fülle das i-te Fach soweit, dass möglichst gut "i * ges/n" dadurch abgearbeitet werden.


Flamefire - Do 14.02.13 19:55

Idee ist sehr gut.
Ich glaube, das passt so.


Flamefire - Do 14.02.13 21:53

Wen es interessiert oder wenn noch jemand verbesserungen hat, hier der (Javascript) Code:
numbers ist ein array von arrays. Die Unterarrays haben an Position 0 den Text, um den es geht.
Rest sollte selbsterklärend sein.

JavaScript-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
function makeMenu(numbers) {
    var elCt=numbers.length;
    if (elCt == 0return;
    var menuUl = document.createElement('ul');
    var catCt = Math.min(elCt, 7);
    var elCatCt = Math.round(elCt / catCt);
    var curStart = 0;
    var curEnd, curEndPre;
    var lastC = numbers[0][0].firstChar();
    var curC;
    for (var i = 1; i < catCt; i++) {
        curEndPre=-100000;
        for (curEnd = curStart + 1; curEnd < elCt; curEnd++) {
            curC = numbers[curEnd][0].firstChar();
            if (curC != lastC) {
                lastC = curC;
                if (curEnd >= i*elCatCt){
                    if(i*elCatCt-curEndPre<curEnd-i*elCatCt) curEnd=curEndPre;
                    break;
                }
                curEndPre=curEnd;
            }
        }
        makeMenuSub(numbers, menuUl, curStart, curEnd-1);
        curStart = curEnd;
        if(curStart>=elCt) break;
    }
    if(curStart+1<elCt) makeMenuSub(numbers, menuUl, curStart, elCt-1);
}


Verbesserungsvorschläge nehme ich gern an. Aber denke, ich hab auch alle Grenzfälle abgedeckt.

Edit: JUHU! Bug im JS-Highlighter!