"faires" Mischen: Algorithmus gesucht (Allgemeines zu Perl)

[thread]19008[/thread]

"faires" Mischen: Algorithmus gesucht

Tags: perl5 Ähnliche Threads

Leser: 18

Articles: hide open all | hide show old branches

+5 replies
Raubtier

2014-04-04 01:40
User since
2012-05-04
1075 Artikel
BenutzerIn
Hallo,

ich bin gerade auf der Suche nach einem Algorithmus, der mir ein Array möglichst gleichmäßig mischt bzw. sortiert derart, dass gleiche Elemente untereinander möglichst weit voneinander entfernt sind.

Beispiel mit 2 unterschiedlichen Elemente, die je 3x vorkommen: aus qw(a a a b b b) soll qw(a b a b a b) oder (gleichwertig gut) qw(b a b a b a) werden.

Interessant wird es, wenn man mehrere Unterschiedliche Elemente hat...

Ich habe bislang folgenden Code:
Code (perl): (dl )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

use strict; use warnings; use feature qw(say); sub fairShuffle { my %count; ++$count{$_} for @_; my @result; for my $key (sort { $count{$a} <=> $count{$b} } keys %count) { my $newLength = @result + $count{$key}; for (1..$count{$key}) { splice @result, (($_-1) * $newLength / $count{$key}), 0, $key; } } return @result; } my @result = fairShuffle(('a') x 5, ('b') x 3, ('c') x 10, ('d') x 1, ('e') x 1); say "@result";
Das Script erzeugt die Ausgabe
Code: (dl )

c a c b c a c b c a c d c a c b c a c e
Wie man sieht, sind die "b"s nicht besonders gut verteilt, dafür sind aber die "c"s perfekt verteilt (das kommt ja durch meine Sortierung oben, die diejenigen Elemente, die am öftesten vorkommen, am Ende verteilt). Andererseits: geht es besser? Gibt es einen einfacheren Algorithmus? Oder einen effizienteren?

Und was ist eine sinnvolle Metrik, um zu bestimmen, ob hier ein Ergebnis gut ist?

Das Ergebnis reicht mir für meinen Einsatzzweck schon aus, aber vielleicht hat hier ja jemand eine bessere Idee.
- +2 replies
- Muffi
  
  2014-04-04 15:13
  
  User since
  2012-07-18
  1465 Artikel
  BenutzerIn
  
  Also als Metrik würd mir spontan sowas einfallen wie:
  
  Abstoßung zwischen 2 gleichen Elementen irgendwas wie 1/Abstand.
  Und dann schaun, dass die Summe aller Abstossungen minimal wird.
  
  PS: Wenn die "c"s perfekt verteilt wären (also mit max. Abstand), dann wär e sicher nicht das letzte Element.
  Last edited: 2014-04-04 15:15:48 +0200 (CEST)
  1 + 1 = 10
  - Raubtier
    
    2014-04-04 15:49
    
    User since
    2012-05-04
    1075 Artikel
    BenutzerIn
    
    2014-04-04T13:13:20 Muffi
    PS: Wenn die "c"s perfekt verteilt wären (also mit max. Abstand), dann wär e sicher nicht das letzte Element.
    
    Ah, ich sollte vielleicht noch hinzufügen, dass man sich das ganze als endloses Band vorstellen soll (modulo Gesamtlänge) :-)
- +2 replies
- hlubenow
  
  2014-04-09 00:40
  User since
  2009-02-22
  875 Artikel
  BenutzerIn
  Ich hab' das mal nach Python übersetzt, um es besser zu verstehen.
  Was ich immer noch nicht tue ...
  
  Code (python): (dl )
  
  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
  
  #!/usr/bin/python def fairShuffle(a): count = {} for i in a: if count.has_key(i): count[i] += 1 else: count[i] = 1 result = [] # Returns a sorted list of the dictionary's keys, # sorted by values, lowest first: for key in sorted(count, key = count.get): newLength = len(result) + count[key] for i in range(1, count[key] + 1, 1): result.insert((i - 1) * newLength / count[key], key) return result a = ["a" * 5, "b" * 3, "c" * 10, "d", "e"] b = [] for i in a: for u in i: b.append(u) c = fairShuffle(b) print " ".join(c)
  
  Spontan dachte ich an "Normalverteilung", aber damit hat das wohl nichts zu tun.
  Woher kennt Dein Algorithmus die "richtigen" Abstände?
  - Raubtier
    
    2014-04-09 01:38
    User since
    2012-05-04
    1075 Artikel
    BenutzerIn
    
    2014-04-08T22:40:03 hlubenow
    Spontan dachte ich an "Normalverteilung", aber damit hat das wohl nichts zu tun.
    Woher kennt Dein Algorithmus die "richtigen" Abstände?
    
    Nee, das hat wirklich nichts mit einer Normalverteilung zu tun. Wobei, wenn wir nur genügend viele Elemente nehmen (Gesetz der großen Threads), ist ja eh alles Gaußisch - oder so ähnlich ;-)
    
    Der Code geht so vor:
    
    Code: (dl )
    
    1 2 3
    
    solange noch neue Elemente da sind: nimm die, die am wenigsten oft da sind verteile sie gleichmäßig in die Ergebnisliste
    
    Das ganze funktioniert natürlich nur, wenn man mit den Elementen anfängt, die weniger oft da sind.
    
    Inzwischen ist mir auch eingefallen, dass ich eigentlich sowas wie einen Scheduler mit Prioritäten haben will (und wohl danach suchen müsste) und nicht nach den Suchbegriffen "fair shuffle"...

View all threads created 2014-04-04 01:40.