Reproducción aleatoria de archivos con algunas restricciones adicionales

Tengo una gran lista de reproducción de música y, aunque algunos artistas tienen muchos álbumes, otros solo tienen una canción. Quería ordenar la lista de reproducción para que el mismo artista no tocara dos veces seguidas, o sus canciones no terminarían principalmente al principio o al final de la lista de reproducción.

Ejemplo de lista de reproducción:

$ cat /tmp/playlist.m3u
Anna A. - Song 1
Anna A. - Song 2
I--Rock - Song 1
John B. - Song 1
John B. - Song 2
John B. - Song 3
John B. - Song 4
John B. - Song 5
Kyle C. - Song 1
U--Rock - Song 1

Salida de sort -Ro shuf:

$ sort -R /tmp/playlist.m3u
Anna A. - Song 1 #
U--Rock - Song 1
Anna A. - Song 2 # Anna's songs are all in the beginning.
John B. - Song 2
I--Rock - Song 1
John B. - Song 1
Kyle C. - Song 1
John B. - Song 4 #
John B. - Song 3 #
John B. - Song 5 # Three of John's songs in a row.

Lo que estoy esperando:

$ some_command /tmp/playlist.m3u
John B. - Song 1
Anna A. - Song 1
John B. - Song 2
I--Rock - Song 1
John B. - Song 3
Kyle C. - Song 1
Anna A. - Song 2
John B. - Song 4
U--Rock - Song 1
John B. - Song 5

Si tuviera que aplicar esa barajadura a una baraja de naipes, creo que primero barajaría la baraja, luego mostraría las cartas en una fila ante mis ojos y procesaría de izquierda a derecha, donde haya clubes o corazones adyacentes. . mover todos menos uno de ellos al azar a otro lugar (aunque no al lado de otro del mismo tipo).

Por ejemplo, con una mano como

🂡 🂢 🂣 🂤 🂥 🂦 🂧 🂨 🂱 🂲 🂳 🃁 🃂 🃃 🃑 🃒

Después de barajar básico:

🂣 🃑 🂲 🂦 🂳 🃁<🂧 🂡 🂨>🃂<🂤 🂢>🃃 🂱 🂥 🃒
                   1  2       3

dos grupos de espadas adyacentes, necesitamos reubicar 1, 2 y 3. Para 1, las opciones son:

🂣 🃑 🂲 🂦 🂳 🃁 🂧 🂡 🂨 🃂 🂤 🂢 🃃 🂱 🂥 🃒
    ↑        ↑                    ↑        ↑

Elegimos uno al azar de esos 4. Luego repetimos el proceso para 2 y 3.

Implementado en perleso sería:

shuf list | perl -e '
  @songs = map {/(.*?)-/; [$1,$_]} <>;
  for ($i = 0; $i < @songs; $i++) {
    if (($author = $songs[$i]->[0]) eq $previous) {
      my @reloc_candidates, $same;
      for($j = 0; $j < @songs; $j++) {
        # build a list of positions where we could move that song to
        if ($songs[$j]->[0] eq $author) {$same = 1} else {
          push @reloc_candidates, $j unless $same;
          $same = 0;
        }
      }
      push @reloc_candidates, $j unless $same;

      if (@reloc_candidates) {
        # now pick one of them at random:
        my $chosen = $reloc_candidates[int(rand(@reloc_candidates))];
        splice @songs, $chosen - ($chosen > $i), 0, splice @songs, $i, 1;
        $i -= $chosen > $i;
      }
    }
    $previous = $author;
  }
  print map {$_->[1]} @songs'

Encontrará una solución con artistas no adyacentes si existe (a menos que más de la mitad de las canciones sean del mismo artista), y debe ser uniforme AFAICT.

Sus datos y restricciones de ejemplo en realidad solo permiten algunas soluciones: debe tocar John B. en cualquier otra canción, por ejemplo. Asumiré que tu lista de reproducción completa real no es esencialmente John B, con otras cosas al azar para dividirla .

Este es otro enfoque aleatorio. A diferencia de la solución de @ frostschutz, se ejecuta rápidamente. Sin embargo, no garantiza un resultado que coincida con sus criterios. También presento un segundo enfoque, que funciona en sus datos de ejemplo, pero sospecho que producirá malos resultados en sus datos reales. Con sus datos reales (ofuscados), agrego el enfoque 3, que es un azar uniforme, excepto que evita dos canciones del mismo artista en una fila. Tenga en cuenta que solo hace 5 "sorteos" en el "mazo" de las canciones restantes, si después de eso todavía se enfrenta a un artista duplicado, emitirá esa canción de todos modos, de esta manera, se garantiza que el programa realmente terminará.

Enfoque 1

Básicamente, genera una lista de reproducción en cada punto, preguntando "¿de qué artistas todavía tengo canciones sin reproducir?" Luego elegir un artista al azar, y finalmente una canción al azar de ese artista. (Es decir, cada artista tiene una ponderación igual, no en proporción al número de canciones).

Pruébelo en su lista de reproducción real y vea si produce mejores resultados que al azar uniforme.

Uso:./script-file < input.m3u > output.m3u Asegúrese de chmod +xello, por supuesto. Tenga en cuenta que no maneja la línea de firma que está en la parte superior de algunos archivos M3U correctamente ... pero su ejemplo no tenía eso.

#!/usr/bin/perl
use warnings qw(all);
use strict;

use List::Util qw(shuffle);

# split the input playlist by artist
my %by_artist;
while (defined(my $line = <>)) {
    my $artist = ($line =~ /^(.+?) - /)
        ? $1
        : 'UNKNOWN';
    push @{$by_artist{$artist}}, $line;
}

# sort each artist's songs randomly
foreach my $l (values %by_artist) {
    @$l = shuffle @$l;
}

# pick a random artist, spit out their "last" (remeber: in random order)
# song, remove from the list. If empty, remove artist. Repeat until no
# artists left.
while (%by_artist) {
    my @a_avail = keys %by_artist;
    my $a = $a_avail[int rand @a_avail];
    my $songs = $by_artist{$a};
    print pop @$songs;
    @$songs or delete $by_artist{$a};
}

Enfoque 2

Como segundo enfoque, en lugar de elegir un artista al azar , puede usar elegir el artista con más canciones, que tampoco es el último artista que elegimos . El párrafo final del programa se convierte en:

# pick the artist with the most songs who isn't the last artist, spit
# out their "last" (remeber: in random order) song, remove from the
# list. If empty, remove artist. Repeat until no artists left.
my $last_a;
while (%by_artist) {
    my %counts = map { $_, scalar(@{$by_artist{$_}}) } keys %by_artist;
    my @sorted = sort { $counts{$b} <=> $counts{$a} } shuffle keys %by_artist;
    my $a = (1 == @sorted)
        ? $sorted[0]
        : (defined $last_a && $last_a eq $sorted[0])
            ? $sorted[1]
            : $sorted[0];
    $last_a = $a;
    my $songs = $by_artist{$a};
    print pop @$songs;
    @$songs or delete $by_artist{$a};
}

El resto del programa permanece igual. Tenga en cuenta que esta no es la forma más eficiente de hacerlo, pero debería ser lo suficientemente rápida para listas de reproducción de cualquier tamaño razonable. Con sus datos de ejemplo, todas las listas de reproducción generadas comenzarán con una canción de John B., luego una canción de Anna A., luego una canción de John B. Después de eso, es mucho menos predecible (ya que a todos menos a John B. le queda una canción). Tenga en cuenta que esto supone Perl 5.7 o posterior.

Enfoque 3

El uso es el mismo que el anterior 2. Tenga en cuenta la 0..4parte, de ahí proviene el máximo de 5 intentos. Podría aumentar el número de intentos, por ejemplo, 0..9daría 10 en total. ( 0..4= 0, 1, 2, 3, 4, lo que notarás es en realidad 5 elementos).

#!/usr/bin/perl
use warnings qw(all);
use strict;

# read in playlist
my @songs = <>;

# Pick one randomly. Check if its the same artist as the previous song.
# If it is, try another random one. Try again 4 times (5 total). If its
# still the same, accept it anyway.
my $last_artist;
while (@songs) {
    my ($song_idx, $artist);
    for (0..4) {
        $song_idx = int rand @songs;
        $songs[$song_idx] =~ /^(.+?) - /;
        $artist = $1;
        last unless defined $last_artist;
        last unless defined $artist; # assume unknown are all different
        last if $last_artist ne $artist;
    }

    $last_artist = $artist;
    print splice(@songs, $song_idx, 1);
}

Si no te importa que sea terriblemente ineficiente ...

while [ 1 ]
do
    R="`shuf playlist`"
    D="`echo "$R" | sed -e 's/ - .*//' | uniq -c -d`"
    if [ "$D" == "" ]
    then
        break
    #else # DEBUG ONLY:
    #    echo --- FAIL: ---
    #    echo "$D"
    #    echo -------------
    fi
done

echo "$R"

Simplemente sigue rodando y rodando hasta que encuentra un resultado que no tiene dos o más Johns seguidos. Si hay tantos Johns en tu lista de reproducción que dicha combinación no existe o es extremadamente improbable que se lance, bueno, se bloqueará.

Ejemplo de resultado con su entrada:

John B. - Song 4
Kyle C. - Song 1
Anna A. - Song 2
John B. - Song 3
Anna A. - Song 1
John B. - Song 1
U--Rock - Song 1
John B. - Song 2
I--Rock - Song 1
John B. - Song 5

Si descomenta las líneas de depuración, le dirá por qué falló:

--- FAIL: ---
      3 John B.
-------------
--- FAIL: ---
      2 John B.
      2 John B.
-------------

Eso debería ayudar a determinar la causa en caso de que se cuelgue indefinidamente.

Otro enfoque usando Bash. Lee la lista de reproducción en orden aleatorio, intenta insertar la línea en el otro extremo de la lista si es un duplicado y deja a un lado a un lado para volver a insertarla en otro lugar. Falla si hay duplicados triples (primero, último y aparte idéntico) y agregará esas entradas incorrectas al final de la lista. Parece ser capaz de resolver la extensa lista que cargó la mayor parte del tiempo.

#!/bin/bash

first_artist=''
last_artist=''
bad_artist=''
bad_line=''
result=''
bad_result=''

while read line
do
    artist=${line/ - */}
    line="$line"$'\n'

    if [ "$artist" != "$first_artist" ]
    then
        result="$line""$result"
        first_artist="$artist"

        # special case: first = last
        if [ "$last_artist" == '' ]
        then
            last_artist="$artist"
        fi

        # try reinserting bad
        if [ "$bad_artist" != '' -a "$bad_artist" != "$first_artist" ]
        then
            first_artist="$bad_artist"
            result="$bad_line""$result"
            bad_artist=''
            bad_line=''
        fi
    elif [ "$artist" != "$last_artist" ]
    then
        result="$result""$line"
        last_artist="$artist"

        # try reinserting bad
        if [ "$bad_artist" != '' -a "$bad_artist" != "$last_artist" ]
        then
            last_artist="$bad_artist"
            result="$result""$bad_line"
            bad_artist=''
            bad_line=''
        fi
    else
        if [ "$bad_artist" == '' ]
        then
            bad_artist="$artist"
            bad_line="$line"
        else
            # first, last and bad are the same artist :(
            bad_result="$bad_result""$line"
        fi
    fi
done < <(shuf playlist)

# leftovers?
if [ "$bad_artist" != '' ]
then
    bad_result="$bad_result""$bad_line"
fi

echo -n "$result"
echo -n "$bad_result"

Podría ser más inteligente ... en su ejemplo de John, John generalmente se mantendrá como el último artista porque siempre trata de agregar el primer artista primero. Entonces, si hay otros dos artistas en el medio, no es lo suficientemente inteligente como para agregar uno al principio y el otro al final para evitar el triple-John. Entonces, con listas que básicamente requieren que cada otro artista sea John, obtienes más fracasos de los que deberías.