Autor Beitrag
Flamefire
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Do 14.02.13 16:17 
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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8535
Erhaltene Danke: 473

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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

ausblenden 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.

_________________
We are, we were and will not be.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Do 14.02.13 19:55 
Idee ist sehr gut.
Ich glaube, das passt so.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: 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.
ausblenden 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!