Ich habe ein Algorithmusproblem, an dem ich verzweifelt knacke. Erstmal die Rahmenbedingung:
Aus einer Datenbank lese ich Objektdaten (items), welche aus einer ID und einer zeitlichen Längenangabe bestehen (also ID: 6, 300 Sekunden). Aufgabe ist es nun, diese items nach festen regeln „zufällig“ zu mischen und hintereinander aufzulisten. Am Ende soll sich eine zufallsgenerierte Zeitskala ergeben, z.B.:
(6, 300), (1, 233), (77, 458) usw.
Wichtig ist, dass die Liste an items, die aus der Datenbank kommt, mehrfach die selbe ID enthalten kann (ich weiß, dann ist es keine echte ID … ist auch nicht der Primärschlüssel).
Die Regeln sind nun folgende:
-
Die Zeitskala soll in einer definierten Länge sein (nicht alle items müssen verwendet werden, nur so viele, um die Skala zu füllen) -> z.B. 3600 Sekunden
(kleine Überschreitungen sind erlaubt) -
jedes item aus der Datenbankliste darf nur einmal gewählt werden (es wird beim Einfügen aus der Auswahl entfernt)
-
keine zwei items mit der selben id direkt nebeneinander
-
nur n-viele items mit der selben id pro Zeitabschnitt (also etwa: gesamte Skala 3600 Sekunden, jedes Item aber nur einmal pro 1200 Sekunden)
-
weil es nicht genug ist: es gibt in der Menge aller items speziell markierte (wenige), welche auf jeden Fall auf der Zeitskala auftauchen müssen
Nun ist es klar, dass die Parameter so gewählt werden könnten oder die Daten so beschaffen sind, dass es keine Lösung gibt, z.B. wenn
- wenn alle vorhandenen items die Zeit nicht füllen können
- zu viele item mit gleicher id vorhanden sind, aber nicht so häufig in einem Abschnitt auftauchen dürfen
Zu meinen Ansätzen:
- Zunächst stelle ich mir eine Liste zusammen, die alle speziell markierten items enthält und fülle sie mit zufälligen aus der Restliste auf, bis die gewünschte Zeit erreicht ist.
Jeder Versuch, aus dieser Auswahl eine Liste so anzuordnen, dass die Zeitbeschränkung immer eingehalten wird, artet bei jedem notwendigem Tausch zu Brute Force aus.
Daher folgende Idee:
- Ich zähle die Anzahl der gleichen Ids. Die höchste Anzahl bestimmt die Menge an Teillisten, die ich benutze (z.b. 4).
- 5 leere Teillisten eröffnen und diejenigen items, die 4x gezählt wurden an deren Anfang einfügen
- Die nächst größte item-Gruppierung nehmen (z.b. 3) und an die bestehenden 4 Teillisten anhängen
- Schritt 3 mit allen Gruppierungen wiederholen, bis alle items verteilt sind
- alle Teillisten zu einer Liste/ Zeitskala zusammenfügen
Als Beispiel:
itemIDs vorher: 5 5 5 5 4 4 4 3 3 2 1
itemIDs Teillisten: 5432
5431
54
5
Teillisten zusammen: 5 4 3 2 5 4 3 1 5 4 5
Die Teillisten sorgen dafür, dass die häufigsten Elemente möglichst weit auseinanderstehen. In dem Algorithmus spielt die Zeit noch keine Rolle. Damit nicht Teillisten entstehen, die zu kurz oder lang werden, wird beim Einfügen in die Teilliste noch folgende Regel beachtet:
- Einfügen in die Teilliste, welche in der Summe der Zeit am kürzesten ist, solange nicht schon ein item mit gleicher id darin enthalten ist.
Wer bis hierhin gelesen hat, erntet schon Dank von mir für seine Geduld 
Die Probleme an meinem Ansatz sind:
- nicht allzu zufällige Konstellation (nicht allzu schlimm!)
- Aus dem Algorithmus heraus erkenne ich noch nicht, ob alle gleiche Items wirklich weit genug auseinanderstehen (also ob er gescheitert ist)
- das allergrößte Problem: wenn ich erkenne, dass er gescheitert ist, dann könnte es an der Auswahl der items liegen. Hätte ich aus der ursprünglichen Datenbankliste andere gewählt, hätte es vielleicht geklappt …
Danke für jeden, der sich damit schon beschäftigt hat und noch Lust verspürt, sich ein paar Gedanken zu machen!