Mélangez le fichier de manière aléatoire avec des contraintes supplémentaires

12

J'ai une énorme liste de lecture de musique et, alors que certains artistes ont de nombreux albums, d'autres n'ont qu'une seule chanson. Je voulais trier la playlist pour que le même artiste ne joue pas deux fois de suite, ou que ses chansons ne se retrouvent pas principalement au début ou à la fin de la playlist.

Exemple de liste de lecture:

$ 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

Sortie de sort -Rou 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.

Ce que j'attends:

$ 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
Teresa e Junior
la source
13
Techniquement, ce que vous demandez, c'est moins de hasard et plus de structure. Ce n'est pas impossible, mais cela nécessitera un script (bash / awk / perl / python / etc).
goldilocks
Ou un hasard structuré :)
Teresa e Junior
Exactement! Ce serait un bon exercice en perl ou en python. Je pense que ce serait un casse-tête avec bash, même si cela pourrait bien fonctionner avec awk - je ne connais pas assez bien awk pour le dire.
goldilocks
Puisqu'il ne semble pas y avoir d'outils pour le faire, un script semble être la voie à suivre. Ce n'est pas que je suis paresseux, mais je suis à court d'idées.
Teresa e Junior
1
Vous pourriez être en mesure de le faire avec un algorithme simple: créez la liste de lecture en sélectionnant une chanson aléatoire par chaque artiste à son tour (où le tour peut également être randomisé mais sans répétition d'artiste). Lorsque toutes les chansons d'un artiste ont été épuisées, commencez à entrelacer les chansons des artistes restants (encore une fois, en alternant entre elles à tour de rôle) avec la liste de lecture existante de manière à minimiser la contiguïté des chansons du même artiste. Continuez à répéter jusqu'à ce que vous ayez terminé. Je suis désolé de n'avoir pas le temps de faire un tour dans un vrai script; J'ai juste pensé qu'il pourrait être utile de vous aider à lancer le vôtre.
Joseph R.

Réponses:

5

Si je devais appliquer ce mélange à un jeu de cartes à jouer, je pense que je mélangerais d'abord le jeu, puis afficherais les cartes d'affilée devant mes yeux et les traiterais de gauche à droite, partout où il y a des clubs ou des cœurs adjacents .. . déplacez tous ceux sauf un au hasard ailleurs (mais pas à côté d'un autre du même type).

Par exemple, avec une main comme

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

Après un brassage de base:

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

deux groupes de piques adjacents, nous devons déplacer 1, 2 et 3. Pour 1, les choix sont:

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

Nous en choisissons un au hasard parmi ces 4. Ensuite, nous répétons le processus pour 2 et 3.

Mis en œuvre dans perlce serait:

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'

Il trouvera une solution avec des artistes non adjacents s'il existe (à moins que plus de la moitié des chansons soient du même artiste), et devrait être uniforme AFAICT.

Stéphane Chazelas
la source
En essayant les trois scripts différents (perl et bash), tous mélangent la liste de lecture que j'ai laissée sur pastebin sans laisser de chansons adjacentes, mais la vôtre semble le faire de manière plus intelligente. D'ailleurs, seul le vôtre fonctionne parfaitement sur l' exemple de John B. , ce qui en fait sans aucun doute une meilleure réponse. J'ai promis à derobert d'accepter sa réponse, car il était si patient et serviable avec moi, et sa troisième approche est également très bonne. Je vais donc vous donner la meilleure réponse et la prime à lui, et j'espère qu'il ne se fâche pas contre moi :)
Teresa e Junior
7

Vos données et contraintes d'exemple ne permettent en fait que quelques solutions - vous devez jouer John B. toutes les autres chansons, par exemple. Je vais supposer que votre liste de lecture complète n'est pas essentiellement John B, avec d'autres choses aléatoires pour le casser .

Ceci est une autre approche aléatoire. Contrairement à la solution de @ frostschutz, elle s'exécute rapidement. Cependant, cela ne garantit pas un résultat qui correspond à vos critères. Je présente également une deuxième approche, qui fonctionne sur vos données d'exemple, mais je pense que cela produira de mauvais résultats sur vos données réelles. Ayant vos vraies données (obscurcies), j'ajoute l'approche 3 - qui est un aléatoire uniforme, sauf qu'elle évite deux chansons du même artiste d'affilée. Notez qu'il ne fait que 5 "tirages" dans le "deck" des chansons restantes, si après cela, il est toujours confronté à un artiste en double, il sortira cette chanson de toute façon - de cette façon, sa garantie que le programme se terminera réellement.

Approche 1

Fondamentalement, il génère une liste de lecture à chaque point, demandant "de quels artistes ai-je encore des chansons non jouées?" Puis choisir un artiste au hasard, et enfin une chanson au hasard de cet artiste. (C'est-à-dire que chaque artiste est pondéré de manière égale, non proportionnellement au nombre de chansons.)

Essayez-le sur votre liste de lecture réelle et voyez si elle produit de meilleurs résultats que uniformément aléatoire.

Utilisation:./script-file < input.m3u > output.m3u assurez-vous chmod +xbien sûr. Notez qu'il ne gère pas correctement la ligne de signature qui se trouve en haut de certains fichiers M3U ... mais votre exemple ne l'a pas.

#!/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};
}

Approche 2

Dans une deuxième approche, au lieu de choisir un artiste au hasard , vous pouvez utiliser choisir l'artiste avec le plus de chansons, qui n'est pas non plus le dernier artiste que nous avons choisi . Le dernier paragraphe du programme devient alors:

# 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};
}

Le reste du programme reste le même. Notez que ce n'est de loin pas le moyen le plus efficace de le faire, mais il devrait être assez rapide pour les listes de lecture de toute taille saine. Avec vos données d'exemple, toutes les listes de lecture générées commenceront par une chanson de John B., puis une chanson d'Anna A., puis une chanson de John B. Après cela, c'est beaucoup moins prévisible (comme tout le monde sauf John B. a une chanson). Notez que cela suppose Perl 5.7 ou une version ultérieure.

Approche 3

L'utilisation est la même que la précédente. Notez la 0..4partie, c'est de là que viennent les 5 essais max. Vous pourriez augmenter le nombre d'essais, par exemple, 0..9donner 10 au total. ( 0..4= 0, 1, 2, 3, 4, ce que vous remarquerez est en fait 5 articles).

#!/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);
}
derobert
la source
@TeresaeJunior avez-vous essayé les deux programmes sur les données réelles et voyez si l'un ou l'autre vous convient? (Et, wow, en regardant ça, c'est très "Fhk Hhck" lourd ... je vais ajouter une approche 3)
derobert
Certains artistes jouent en fait deux fois de suite (vous pouvez le vérifier avec sed 's/ - .*//' output.m3u | uniq -d). Et pourriez-vous s'il vous plaît expliquer si cela prend en charge certains artistes ne se retrouvant pas au début ou à la fin de la playlist?
Teresa e Junior
L'approche 1 permet en effet deux (ou plus) d'affilée. L'approche 2 ne le fait pas. L'approche 3 (sur le point de l'éditer) ne le fait pas non plus (enfin, surtout). Approach 2 pondère définitivement le début de la playlist des artistes les plus connus. L'approche 3 ne le sera pas.
derobert
1
@TeresaeJunior Je suis content que le troisième ait fonctionné! Je ne sais pas exactement quelle aurait été l'approche 4, mais ce serait effrayant ...
derobert
1
@JosephR. Approche # 3 n'utiliser le nombre de chansons de chaque artiste comme un poids implicitement, en choisissant une chanson au hasard. Plus un artiste a de chansons, plus il est probable qu'il soit choisi. # 1 est le seul qui ne pèse pas en nombre de chansons.
derobert
2

Si cela ne vous dérange pas d'être horriblement inefficace ...

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"

Il continue de rouler et de rouler jusqu'à ce qu'il arrive sur un résultat qui n'a pas deux ou plusieurs Johns d'affilée. S'il y a tellement de Johns dans votre liste de lecture qu'une telle combinaison n'existe pas ou qu'il est extrêmement peu probable qu'elle soit roulée, eh bien, elle se bloquera.

Exemple de résultat avec votre entrée:

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 vous décommentez les lignes de débogage, il vous expliquera pourquoi il a échoué:

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

Cela devrait aider à déterminer la cause au cas où il se bloquerait indéfiniment.

frostschutz
la source
J'aime l'idée, mais le script fonctionne depuis près de 15 mètres et n'a pas pu trouver de combinaison appropriée. Ce n'est pas que j'ai trop de chansons de John, mais la liste de lecture est plus de 7000 lignes, et il semble que ce soit comme ça sort.
Teresa e Junior
1
En ce qui concerne les performances, shufmélange la liste de lecture 80 fois plus rapidement que sort -R. Je ne le savais pas non plus! Je vais le laisser tourner 15 minutes avec shuf, les chances sont plus grandes!
Teresa e Junior
Déboguer, echo "$D"avant le if. Cela devrait vous dire quels doublons ont empêché le choix du résultat. Cela devrait vous dire où chercher le problème. (Edit: Ajout d'un code de débogage possible à la réponse.)
frostschutz
DEBUG affiche toujours environ 100 lignes, mais d'artistes aléatoires, il semble donc que beaucoup d'artistes causent le problème. Je pense que ce n'est pas vraiment possible avec sortou shuf.
Teresa e Junior
1

Une autre approche utilisant Bash. Il lit la liste de lecture dans un ordre aléatoire, essaie d'insérer la ligne à l'autre extrémité de la liste s'il s'agit d'un doublon, et met une seule dupe de côté pour la réinsérer dans un autre endroit. Il échoue s'il y a trois doublons (premier, dernier et mis de côté identiques) et il ajoutera ces entrées incorrectes à la fin de la liste. Il semble être en mesure de résoudre la longue liste que vous avez téléchargée la plupart du temps.

#!/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"

Cela pourrait être plus intelligent ... dans votre exemple John, John s'en tiendra généralement au dernier_artiste car il essaie toujours d'ajouter le premier_artiste en premier. Donc, s'il y a deux autres artistes entre les deux, ce n'est pas assez intelligent pour ajouter l'un au début et l'autre à la fin pour éviter le triple-John. Donc, avec des listes qui exigent essentiellement que tous les autres artistes soient John, vous obtenez plus d'échecs que vous ne devriez.

frostschutz
la source
Merci pour ce script bash. C'est le seul que je puisse vraiment comprendre et modifier à volonté!
Teresa e Junior