Stringlist in zufällige Reihenfolge bringen

[Maekkelrajter]

Ich brüte z. Z. an einem kniffligen Problem: gegeben eine Stringlist mit 400 Strings, von denen etliche mehrfach (bis zu 30 mal) vorkommen. Daraus soll eine Zufalls-Liste generiert werden.
Der Hintergrund: Aus einer nach Interpret sortierten Playliste soll eine Liste generiert werden, in der die Reihenfolge der Interpreten 'zufällig' ist.
Eigentlich kein Problem, sollte man meinen

Delphi-Quellcode:

 //var SL: TStringlist
for i := SL.Count-1 downto 1 do SL.Exchange(i, random(i+1));

Die so erzeugte Mischung ist eigentlich schon recht zufriedenstellend, aber es gibt noch einen Schönheitsfehler: Es kommt mehrfach vor, dass zwei gleichlautende Einträge unmittelbar aufeinander folgen. Wie kann ich das unterbinden? Gibt es einen (Zufalls-) Algorithmus, mit dem man das verhindern könnte, oder muss ich die erzeugte 'Zufalls' - Liste (evtl. mit einem eigenen Algorithmus) nachbearbeiten?

Gruß LP

[peterbelow]

Einen generell anwendbaren Algorithmus für dieses Problem kann es kaum geben denn es hängt stark vom Inhalt der Quelliste ab, ob es überhaupt eine solche Lösung gibt. Vermutlich ist es für Dich am einfachsten einen zweiten Durchlauf über die "randomisierte" Liste zu machen und dabei nach "Dubletten" zu suchen. Wenn Du eine findest such für einen der beiden Einträge nach einem besseren Platz in der Liste und verschiebe ihn dahin. Falls sich kein solcher Platz findet gib auf und leb' damit.

[Gausi]

Du musst dich entscheiden: Entweder eine zufällige Liste, oder eine nicht-zufällige Liste. Bei zufälligem durcheinanderwürfeln wird es in deinem Szenario praktisch immer vorkommen, dass zwei gleiche Elemente (fast) direkt aufeinanderfolgen.

Ähnliche Probleme gibt es z.B. auch bei der Zufalls-Reihenfolge bei Playlists (da wird es auch oft zu Doppelungen kommen, bevor alle Titel einmal abgespielt wurden). Ebenso ist die Wahrscheinlichkeit, dass in einer Klasse von 23 Schülern zwei am gleichen Tag Geburtstag haben, schon über 50%, obwohl das Jahr 365 Tage hat, und nicht nur "etwas mehr als 23".

Also: Wenn du keine zwei gleichen Elemente hintereinander haben willst, musst du "nachbearbeiten". Bei anscheinend so vielen Mehrfach-Einträgen wird dann aber nicht mehr viel "Zufall" übrig bleiben, fürchte ich.

[Blup]

Vorschlag:

1. merke dir alle mehrfach vorkommende Titel und deren Anzahl
2. lösche die mehrfachen Titel, so dass jeder Titel nur einmal vorkommt.
3. mische die Liste
4. Füge die mehrfachen Titel zufällig einzeln ein.
Dabei sind nur Positionen zulässig, die nicht unmittelbar vor oder nach dem gleichen Titel liegen.

- Angenommen die Liste hat (a) Einträge.
- damit gibt es (a + 1) Positionen, an die der neue Eintrag eingefügt werden kann
- für jeden gleichen Titel, der bereits in der Liste ist, verringert sich die Anzahl der Positionen um 2: (a + 1 - 2b)

Delphi-Quellcode:

procedure MehrfachTitelEinfuegen(AList: TStringList; const ATitel: string; ACount: Integer);
begin
  for var b := 1 to ACount do
  begin
    var pos := Rand(AList.Count + 1 - 2 * b);
    {ungültige Positionen überspringen}
    for n := 0 to AList.Count - 1 do
    begin
      if AList(n) = ATitel then
        Inc(pos, 2);
      
      if n = pos then
        Break;
    end;
    Alist.Insert(pos, ATitel);
  end;
end;

[Uwe Raabe]

Anstatt die Liste selbst zu manipulieren kannst du auch per Zufall ein Element der Liste auswählen und es an eine neue Liste anhängen und aus der Ausgangsliste entfernen bis sie leer ist. Falls es am Ende der Liste nicht passen sollte, kannst du es für später drin lassen oder an eine passende Stelle in der neuen Liste einfügen.

[himitsu]

* du könntest die Liste in 30 Teile Gruppen aufteilen, oder eine gemeinsame vielfache Anzahl der Doppelten/Mehrfachen

* dann alle Mehrfachen auf die Gruppen aufteilen
* * gleichmäßig oder per Zufall (maximal/möglichst nur je Einer pro Gruppe)

* zum Schluss die Gruppen mit den nichtmehrfachen halbwegs gleichmäßig auffüllen
* * jeweils kleinste Gruppe suchen und per Zufall einen der Einzelnen da rein
* * bis alle verteilt sind

* nun die Inhalte der Gruppen sortieren
* die Gruppen untereinander umsortieren, besser nicht, weil dann die vorherrige Aufteilung sich wieder zufällig zusammenfinden könnte
* eventuell schauen ob in benachbarten Gruppen was zu nah zusammen und diese Beiden oder eine der Beiden neu sortieren
* * wiederholen bis OK, oder zuviele Versuche und aufgeben

* und nun die Gruppen






Oder beim Umsortieren (der gesamten Liste) jeweils schauen, ob am Ziel in der Nähe zuviele Gleiche liegen und dann dieses Austauschen der Beiden nicht machen.

Delphi-Quellcode:

for j := 0 to 10 do  // mehrmals durch
  for i := SL.Count-1 downto 1 do begin
    x := random(i+1);
    if PrüfeAnzahlDerGleichenImBereich(SL, S[i], x-20, x+20) < MaximalSovieleNahZusammen then
      SL.Exchange(i, x); 
  end;

Delphi-Quellcode:

for j := 0 to 1000 do begin
  i := random(i+1);
  x := random(i+1);
  if PrüfeAnzahlDerGleichenImBereich(SL, S[i], x-20, x+20) < MaximalSovieleNahZusammen then
    SL.Exchange(i, x); 
end;

[Michael II]

Wie oben bereits erwähnt wird: Wenn du alle 400 Elemente auf alle Arten zufällig anordnest hast du 400! (nicht notwendig voneinander verschiedene) Listen und bei vielen dieser Listen wirst du auf Wiederholungen treffen.

Du kannst natürlich mit Bastelarbeiten/Korrekturen - wie zum Beispiel oben erwähnt - eine Liste erzeugen, welche keine Wiederholungen aufweist. Bei vielen dieser Basteleien werden gewisse mögliche Listen häufiger auftreten als andere.

Wenn du wirklich eine zufällige Liste gemäss deinen Vorgaben willst, dann solltest du die möglichen Listen (also zum Beispiel all jene, bei welchen keine Wiederholungen auftreten) durchnummerieren. Dann hast zu n mögliche Listen. Bestimme zufällig eine dieser Listen.

Das ist dann mathematisch gesehen korrekt (jede der möglichen Liste tritt dann mit gleicher Wahrscheinlichkeit auf), aber wahrscheinlich für eine Playlist mit etwas viel Aufwand verbunden.

[Kas Ob.]

No sure if I understand the question 100%, but I would solve this by not using for-statement, it will just complicate the restrain the algorithm.
I think "While-do" or "Repeat-until" loop is better approach, something like:

Code:

  while Count < Required do
  begin
    SelectAtRandom;  // from the pot
    if SelectedIsOK then
      begin
        StoreInList;
        Inc(Count);
        // Here we could adjust the selection condition like remove elements from the pot
      end; // else we pick again and ignore the selected
  end;

SelectedIsOK can be be multiple conditions, like simple check if the current pick artist is not the last (or 2nd,3th) artist in the selected list.

[PaPaNi]

Zitat von Uwe Raabe:

Anstatt die Liste selbst zu manipulieren kannst du auch per Zufall ein Element der Liste auswählen und es an eine neue Liste anhängen und aus der Ausgangsliste entfernen bis sie leer ist. Falls es am Ende der Liste nicht passen sollte, kannst du es für später drin lassen oder an eine passende Stelle in der neuen Liste einfügen.

Das ist das Erstes was mir eingefallen ist. Ich würde auch so machen.

[Blup]

Eine funktionierende Lösung:

Delphi-Quellcode:

procedure TitelEinfuegen(AList: TStrings; const ATitel: string; AAnzahl: Integer);
begin
  var pos: Integer := AList.Count + 1 - 2 * AAnzahl;
  if pos < 1 then
    raise Exception.CreateFmt('Der Titel "%s" tritt zu häufig auf.', [ATitel]);

  pos := Random(pos);
  {ungültige Positionen überspringen}
  if AAnzahl > 0 then
  begin
    for var n := 0 to AList.Count - 1 do
    begin
      if AList[n] = ATitel then
        Inc(pos, 2);

      if n = pos then
        Break;
    end;
  end;
  AList.Insert(pos, ATitel);
end;

procedure TitelMischen(AList: TStrings);
begin
  var lItemList1 := TStringList.Create;
  var lItemList2 := TStringList.Create;
  try
    lItemList1.Assign(AList);
    {mehrfache Titel hintereinander}
    lItemList1.Sort;
    {mehrfache Titel in jeder Runde nur einmal einfügen, falls z.B. nur 10xTitelA und 10xTitelB in der Liste}
    var lAnzahl := 0;
    while lItemList1.Count > 0 do
    begin
      var lTitel := '';
      for var n := lItemList1.Count - 1 downto 0 do
      begin
        if lTitel <> lItemList1[n] then
        begin
          lTitel := lItemList1[n];
          TitelEinfuegen(lItemList2, lTitel, lAnzahl);
          lItemList1.Delete(n);
        end;
      end;
      Inc(lAnzahl);
    end;
    AList.Assign(lItemList2);
  finally
    lItemList1.Free;
    lItemList2.Free;
  end;
end;

procedure TForm1.BtnMischenClick(Sender: TObject);
begin
  TitelMischen(MemoTitel.Lines);
end;