"faires" Mischen: Algorithmus gesucht - #174618 (Allgemeines zu Perl)

Raubtier

2014-04-04 01:40

User since
2012-05-04
1070 Artikel
BenutzerIn
[default_avatar]

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 )

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.