Algorithmus-Nuss: Shuffle mit speziellen Regeln .. (vorsicht: lang!)

[Serethos]

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:

1. 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)

2. jedes item aus der Datenbankliste darf nur einmal gewählt werden (es wird beim Einfügen aus der Auswahl entfernt)

3. keine zwei items mit der selben id direkt nebeneinander

4. nur n-viele items mit der selben id pro Zeitabschnitt (also etwa: gesamte Skala 3600 Sekunden, jedes Item aber nur einmal pro 1200 Sekunden)

5. 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
1. wenn alle vorhandenen items die Zeit nicht füllen können
2. zu viele item mit gleicher id vorhanden sind, aber nicht so häufig in einem Abschnitt auftauchen dürfen

Zu meinen Ansätzen:

1. 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:

1. Ich zähle die Anzahl der gleichen Ids. Die höchste Anzahl bestimmt die Menge an Teillisten, die ich benutze (z.b. 4).
2. 5 leere Teillisten eröffnen und diejenigen items, die 4x gezählt wurden an deren Anfang einfügen
3. Die nächst größte item-Gruppierung nehmen (z.b. 3) und an die bestehenden 4 Teillisten anhängen
4. Schritt 3 mit allen Gruppierungen wiederholen, bis alle items verteilt sind
5. 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:

1. nicht allzu zufällige Konstellation (nicht allzu schlimm!)
2. Aus dem Algorithmus heraus erkenne ich noch nicht, ob alle gleiche Items wirklich weit genug auseinanderstehen (also ob er gescheitert ist)
3. 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!

[thordk]

würd dabei sehr straight forward vorgehen.

erstmal wird eine funktion benötigt, die zulässige einfügepositionen M in der liste ermittelt.

1. ermittele alle felder m, deren benachbarte felder m-1 und m+1 nicht mit derselben id belegt sein
2. prüfe für alle positionen M, ob in ihrer nachbarschaft ein item mit derselben zeit vorkommt und entferne sie aus M

- ist die liste leer, füge an zufälliger position ein
- ist M zu irgendeinem zeitpunkt eine leere menge, ist der algorithmus gescheitert.
- ist M nicht leer, wähle zufällig ein m und füge das element an dieser position ein.
- prüfe, ob die gesamtsumme der zeiten die geforderte zeit überschritten hat.

das ganze wird dann erstmal für alle markierten elemente getan. dafür würd ich mir alle markierten elemente holen und anhand ihrer id sortieren. absteigend mit der höchsten anzahl an selben ids beginnend (z.b. 5 5 5 3 3 2 1) elemente mit derselben id werden in zufälliger reihenfolge abgearbeitet, um die wahrscheinlichkeit für kollisionen zu reduzieren.
das erste element wird gemäß des algorithmus an beliebiger stelle eingefügt. die nachfolgenden elemente entsprechend weiter.

sollte die gesamtsumme noch nicht ausreichen, können jetzt die restlichen elemente in zufälliger reihenfolge abgearbeitet werden. ist die liste voll und die summer stimmt, war das ganze erfolgreich. ist die summe zu klein/groß oder es gibt keine elemente in der datenbank mehr, ist das ganze gescheitert.

[D-U-D-E]

Wieso erzeugst du nicht einfach eine zufällige Permutation und nimmst die ersten n Elemente, bis deine Skala voll ist? Geht in O(n)

[thordk]

D-U-D-E schrieb:

Wieso erzeugst du nicht einfach eine zufällige Permutation und nimmst die ersten n Elemente, bis deine Skala voll ist? Geht in O(n)

weil seine zufälligen elemente bestimmten regeln unterliegen müssen, wie im post zu lesen ist

[oelsni]

klingt ziemlich abgefahren hoffe habe es richtig verstanden. Kannst dann auch so machen. wenn du weist was dein gesammt zeit volumen ist und du weist wie weit items mit gleicher id (bei dir in bsp 1200 sek) auseinander liegen, so bau dir doch feste teillisten deren zeit nicht überschritten werden darf. nach der regel kommt dann eben in jede teilliste nur eine itemid (unique). wichtig die teilisten werden in der teilzeit nicht überschritten. am ende kannst eine resteliste bauen die die verbleibende zeit auffüllt. nun das zusammensetzen der teillisten und das sichergehen der 1200 sek differenz das kannst über prioritäten klären. d.h. wenn item(35,315) in der 1. teilliste auf platz 1 steht hat es priorität 1. da die 1200 der teillisten nicht überschritten werden darf, darf demzufolge das selbe item in teilliste 2 nicht die gleiche prirität haben sondern eine niedrigere (1 höchste n niedrigste) also prirität 2 oder kleiner. das garantiert das immernoch ein item dazwischenliegt das die diff-zeit ermöglicht. desweiteren bei einer festen teilliste kannst per zufall so lange an einer teilliste arbeiten biszb. 95% der zeit gefüllt sind (zufällig optimal füllen). das ist zwar mit einer gewissen struktur verbunden aber immernoch zufällig genug. sobald sich eine teilliste nicht füllen lässt ist es fehlgeschlagen. die bedingungen für die teilliste da beziehe ich mich auf thor anders würd ich es dann auch nicht mehr machen. gibt halt da viele wege.

[D-U-D-E]

thordk schrieb:

D-U-D-E schrieb:

Wieso erzeugst du nicht einfach eine zufällige Permutation und nimmst die ersten n Elemente, bis deine Skala voll ist? Geht in O(n)

weil seine zufälligen elemente bestimmten regeln unterliegen müssen, wie im post zu lesen ist

Na gut, dann halt 2x eine Permutation erzeugen

Eingabe: Liste A mit speziellen Items, Liste B mit dem schäbigen Rest
1. Erzeuge eine zufällige und gleichverteilte Permutation von A
2. Falls noch Platz auf der Zeitskala, dann erzeuge zweite (zufällige und gleichverteilte) Permutation aus der Liste B

Regel 1 wird erfüllt.
Regel 2 wird definitiv erfüllt.
Regel 3 auch.
Regel 4 auch (jedes Item tritt genau 1-Mal auf).
Regel 5 auch.

Oder hab ich was falsch verstanden?

[thordk]

wenn du lediglich zwei rein zufällige permutationen erzeugst, kann es passieren, dass beispielsweise die regel, dass zwei elemente mit derselben ID nicht aufeinander folgen dürfen, nicht erfüllt ist.
denke mit einfacher permutation kommt man nicht zum ziel, man muss sich striktere regeln definieren, wie die liste gefüllt wird und extrahieren, wo spielraum für permutation ist. das habe ich in meinem posting versucht.

[D-U-D-E]

Wenn ich 2 disjunkte Listen A und B habe, die dann (permutiert) aufeinanderfolgen, dann wird der Fall, daß 2 gleiche Elemente aufeinanderfolgen, nie eintreten. Oder habe ich was mißverstanden?