Случайно перемешать файл с некоторыми дополнительными ограничениями

У меня огромный музыкальный плейлист, и, хотя у некоторых артистов много альбомов, у других всего одна песня. Я хотел отсортировать плейлист, чтобы один и тот же исполнитель не играл дважды подряд, или его песни не попадают в начало или конец плейлиста.

Пример плейлиста:

$ 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

Выход из sort -Rили 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.

Что я ожидаю:

$ 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

Если бы мне пришлось применить эту перетасовку к колоде игральных карт, я думаю, что я сначала перетасовал колоду, а затем отображал карты подряд перед моими глазами и обрабатывал их слева направо, где бы ни находились смежные булавы или сердце ... Переместить всех, кроме одного наугад, куда-нибудь еще (хотя не рядом с другим того же типа).

Например, с рукой, как

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

После основной тасовки:

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

две группы смежных пик, мы должны переместить 1, 2 и 3. Для 1, выбор:

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

Мы выбираем один случайный из этих 4. Затем мы повторяем процесс для 2 и 3.

Реализовано perlчто бы:

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'

Он найдет решение для несмежных исполнителей, если он существует (если только не более половины песен принадлежат одному исполнителю), и должен быть одинаковым AFAICT.

Ваши примеры данных и ограничения на самом деле допускают только несколько решений - например, вы должны играть Джона Б. каждую другую песню. Я собираюсь предположить, что ваш настоящий полный плейлист не является по сути Джоном Б. со случайным другим материалом, чтобы разбить его .

Это еще один случайный подход. В отличие от решения @ frostschutz, оно работает быстро. Однако это не гарантирует результат, который соответствует вашим критериям. Я также представляю второй подход, который работает с данными вашего примера, но я подозреваю, что он даст плохие результаты на ваших реальных данных. Имея ваши реальные данные (обфусцированные), я добавляю подход 3 - который является равномерным случайным, за исключением того, что он избегает двух песен одного исполнителя подряд. Обратите внимание, что он делает только 5 «дро» в «колоду» оставшихся песен, если после этого он все еще сталкивается с дублирующим исполнителем, он все равно выведет эту песню - таким образом, он гарантированно завершит программу.

Подход 1

По сути, он генерирует плейлист в каждой точке, спрашивая, «от каких исполнителей у меня до сих пор нетигранные песни?» Затем выбираем случайного исполнителя и, наконец, случайную песню этого исполнителя. (То есть каждый исполнитель имеет одинаковый вес, не пропорционально количеству песен.)

Попробуйте его в своем плейлисте и посмотрите, дает ли он лучшие результаты, чем случайный.

Использование:./script-file < input.m3u > output.m3u Убедитесь в chmod +xэтом, конечно. Обратите внимание, что он не обрабатывает строку подписи, которая находится в верхней части некоторых файлов M3U ... но в вашем примере этого не было.

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

Подход 2

В качестве второго подхода вместо выбора случайного исполнителя можно выбрать исполнителя с большинством песен, который также не является последним выбранным исполнителем . Последний пункт программы становится:

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

Остальная часть программы остается прежней. Обратите внимание, что это далеко не самый эффективный способ сделать это, но он должен быть достаточно быстрым для плейлистов любого нормального размера. С вашими примерами все сгенерированные плейлисты начнутся с песни Джона Б., затем песни Анны А., затем песни Джона Б. После этого все гораздо менее предсказуемо (поскольку у всех, кроме Джона Б., осталась одна песня). Обратите внимание, что это предполагает Perl 5.7 или новее.

Подход 3

Использование такое же, как и в предыдущем 2. Обратите внимание на 0..4часть, откуда берется максимум 5 попыток. Вы можете увеличить количество попыток, например, 0..9даст 10 всего. ( 0..4= 0, 1, 2, 3, 4, который вы заметите, на самом деле это 5 пунктов).

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

Если вы не возражаете, это ужасно неэффективно ...

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"

Он просто продолжает катиться, пока не достигнет результата, в котором нет двух или более Джонов подряд. Если в вашем плейлисте так много Johns, что такая комбинация не существует или крайне маловероятно, что она будет выпадать, ну, она будет зависать.

Пример результата с вашими данными:

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

Если вы раскомментируете строки отладки, он скажет вам, почему это не удалось:

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

Это должно помочь определить причину, если она зависает на неопределенный срок.

Другой подход с использованием Bash. Он читает список воспроизведения в произвольном порядке, пытается вставить строку на другом конце списка, если он дубликат, и откладывает один дубликат, чтобы вставить его в другое место. Он потерпит неудачу, если есть тройные дубликаты (первый, последний и выделены идентичные), и он добавит эти плохие записи в самый конец списка. Похоже, что он может решить обширный список, который вы загружали большую часть времени.

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

Это может быть умнее ... в вашем примере с Джоном Джон обычно придерживается позиции last_artist, потому что он всегда пытается сначала добавить first_artist. Таким образом, если между двумя другими художниками окажется недостаточно, он недостаточно умен, чтобы добавить одного в начало, а другого - в конец, чтобы избежать тройного Джона. Так что со списками, которые в основном требуют, чтобы каждый другой художник был Джоном, вы получаете больше неудач, чем должны.