Losowo losuj plik z pewnymi dodatkowymi ograniczeniami

12

Mam ogromną listę odtwarzania muzyki i chociaż niektórzy artyści mają wiele albumów, inni mają tylko jedną piosenkę. Chciałem posortować listę odtwarzania, aby ten sam artysta nie był odtwarzany dwa razy z rzędu lub jego piosenki nie kończyły się głównie na początku lub na końcu listy odtwarzania.

Przykładowa lista odtwarzania:

$ 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

Dane wyjściowe z sort -Rlub 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.

Czego oczekuję:

$ 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
źródło
13
Z technicznego punktu widzenia to, o co prosisz, to mniej przypadkowości i więcej struktury. Nie jest to niemożliwe, ale wymaga skryptu (bash / awk / perl / python / etc).
goldilocks,
Lub uporządkowana przypadkowość :)
Teresa e Junior
Dokładnie! To byłoby dobre ćwiczenie w Perlu lub Pythonie. Myślę, że byłby to ból głowy z uderzeniem, chociaż może działać dobrze z awk - nie wiem wystarczająco dobrze, żeby to powiedzieć.
goldilocks,
Ponieważ wydaje się, że nie ma na to żadnych narzędzi, skrypt wydaje się być dobrym rozwiązaniem. To nie tak, że jestem leniwy, ale brakuje mi pomysłów.
Teresa e Junior
1
Możesz to zrobić za pomocą prostego algorytmu: utwórz listę odtwarzania, wybierając kolejno losowe utwory każdego wykonawcy (w którym kolejność może być również losowa, ale bez powtarzania wykonawcy). Gdy wszystkie utwory jednego wykonawcy zostaną wyczerpane, zacznij przeplatać utwory pozostałych wykonawców (ponownie, naprzemiennie między nimi) z istniejącą listą odtwarzania w taki sposób, aby zminimalizować przyleganie utworów tego samego wykonawcy. Powtarzaj, aż skończysz. Przykro mi, że nie mam czasu, aby przekształcić to w rzeczywisty skrypt; Pomyślałem, że może ci się przydać własny.
Joseph R.

Odpowiedzi:

5

Gdybym musiał zastosować to przetasowanie do talii kart do gry, myślę, że najpierw przetasuję talię, a następnie wyświetlę karty w rzędzie na moich oczach i przetworzę od lewej do prawej, wszędzie tam, gdzie są sąsiednie trefl lub serce. , przenieś wszystkie oprócz jednego losowo w inne miejsce (choć nie obok innego tego samego typu).

Na przykład z taką ręką

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

Po podstawowym tasowaniu:

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

dwie grupy sąsiednich pik, musimy przenieść 1, 2 i 3. Dla 1 wyborów są następujące:

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

Wybieramy jeden losowo z tych 4. Następnie powtarzamy proces dla 2 i 3.

Wdrożono perlby to:

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'

Znajduje rozwiązanie dla artystów niesąsiadujących, jeśli istnieje (chyba że więcej niż połowa piosenek pochodzi od tego samego artysty) i powinna być jednolita AFAICT.

Stéphane Chazelas
źródło
Po wypróbowaniu trzech różnych skryptów (perl i bash) wszystkie z nich tasują listę odtwarzania, którą zostawiłem na pastebin, nie pozostawiając przyległych utworów, ale twój wydaje się robić to w bardziej inteligentny sposób. Poza tym tylko twój działa doskonale na przykładzie Johna B. , co niewątpliwie sprawia, że ​​jest to najlepsza odpowiedź. Obiecałem derobertowi, że zaakceptuje jego odpowiedź, ponieważ był dla mnie bardzo cierpliwy i pomocny, a jego trzecie podejście jest również bardzo dobre. Więc dam ci najlepszą odpowiedź i nagrodę dla niego, i mam nadzieję, że się na mnie nie złości :)
Teresa e Junior
7

Twoje przykładowe dane i ograniczenia w rzeczywistości pozwalają tylko na kilka rozwiązań - na przykład musisz zagrać Johna B. Zakładam, że twoja pełna lista odtwarzania nie jest zasadniczo Johnem B, z losowymi innymi rzeczami, które mogą ją zepsuć .

To kolejne losowe podejście. W przeciwieństwie do rozwiązania @ frostschutz działa szybko. Nie gwarantuje to jednak, że wynik spełni twoje kryteria. Przedstawiam również drugie podejście, które działa na przykładowych danych - ale podejrzewam, że przyniesie złe wyniki na twoich prawdziwych danych. Mając twoje prawdziwe dane (zaciemnione), dodaję podejście 3 - które jest jednolite losowo, z tym wyjątkiem, że unika dwóch piosenek tego samego artysty z rzędu. Zauważ, że powoduje tylko 5 „wciągnięć” do „talii” pozostałych utworów, jeśli po tym nadal będzie musiał zmierzyć się ze zduplikowanym wykonawcą, i tak wyda ten utwór - w ten sposób gwarantuje to, że program faktycznie się zakończy.

Podejście 1

Zasadniczo generuje listę odtwarzania w każdym punkcie, pytając „z jakich artystów nadal mam nieodtwarzane utwory?” Następnie wybranie losowego artysty i wreszcie losowa piosenka tego artysty. (Oznacza to, że każdy artysta ma jednakową wagę, nieproporcjonalną do liczby utworów).

Wypróbuj swoją playlistę i sprawdź, czy przynosi lepsze wyniki niż jednolicie losowy.

Zastosowanie:./script-file < input.m3u > output.m3u Oczywiście, upewnij się chmod +x. Zauważ, że nie obsługuje poprawnie linii podpisu znajdującej się na górze niektórych plików M3U ... ale twój przykład tego nie miał.

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

Podejście 2

Jako drugie podejście, zamiast wybierania losowego artysty , możesz użyć wybrania wykonawcy z największą liczbą piosenek, który nie jest również ostatnim artystą, którego wybraliśmy . Ostatni akapit programu staje się następnie:

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

Reszta programu pozostaje taka sama. Zauważ, że zdecydowanie nie jest to najskuteczniejszy sposób na zrobienie tego, ale powinno być wystarczająco szybkie dla list odtwarzania o rozsądnych rozmiarach. Na podstawie przykładowych danych wszystkie wygenerowane listy odtwarzania zaczną się od piosenki Johna B., potem piosenki Anny A., a następnie piosenki Johna B. Potem jest to znacznie mniej przewidywalne (ponieważ wszyscy oprócz Johna B. ma jeszcze jedną piosenkę). Zauważ, że zakłada to Perl 5.7 lub nowszy.

Podejście 3

Użycie jest takie samo jak w poprzednim 2. Zwróć uwagę na 0..4część, z której pochodzi 5 maks. Prób. Możesz zwiększyć liczbę prób, np. 0..9Dałbyś 10 ogółem. ( 0..4= 0, 1, 2, 3, 4, które zauważysz, to w rzeczywistości 5 pozycji).

#!/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
źródło
@TeresaeJunior, czy wypróbowałeś dwa programy na rzeczywistych danych i zobaczyłeś, czy któryś z nich Ci się podoba? (I, wow, patrząc na to, to jest bardzo "Fhk Hhck" ciężkie ... Dodam podejście 3)
derobert
Niektórzy artyści faktycznie grają dwa razy z rzędu (możesz to sprawdzić sed 's/ - .*//' output.m3u | uniq -d). Czy możesz wyjaśnić, czy dba o to, aby niektórzy artyści nie znaleźli się na początku ani na końcu listy odtwarzania?
Teresa e Junior
Podejście 1 rzeczywiście dopuszcza dwa (lub więcej) z rzędu. Podejście 2 nie. Podejście 3 (w celu jego edycji) również nie (cóż, głównie). Podejście 2 zdecydowanie waży na początku listy odtwarzania najpopularniejszych artystów. Podejście 3 nie będzie.
derobert
1
@TeresaeJunior Cieszę się, że trzeci zadziałał! Nie jestem pewien, jakie dokładnie byłoby podejście 4, ale byłoby przerażające ...
derobert
1
@JosephR. # 3 podejść nie używać liczbę piosenek przez każdego artysty jako wagi w sposób dorozumiany, przez podniesienie losowy utwór. Im więcej piosenek ma artysta, tym bardziej prawdopodobne jest, że artysta zostanie wybrany. # 1 jest jedynym, który nie ma wpływu na liczbę utworów.
derobert
2

Jeśli nie masz nic przeciwko temu, że jest okropnie nieefektywny ...

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"

Po prostu toczy się i toczy się, aż dojdzie do wyniku, w którym nie ma dwóch lub więcej Johns z rzędu. Jeśli na twojej liście odtwarzania jest tak dużo Johns, że taka kombinacja nie istnieje lub jest bardzo mało prawdopodobne, aby została rzucona, to się zawiesi.

Przykład wyniku z wprowadzonymi danymi:

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

Jeśli odkomentujesz linie debugowania, powie ci, dlaczego nie powiodło się:

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

To powinno pomóc ustalić przyczynę w przypadku, gdy zawiesza się na czas nieokreślony.

frostschutz
źródło
Podoba mi się ten pomysł, ale skrypt działa prawie 15 metrów i nie mogę znaleźć odpowiedniej kombinacji. Nie chodzi o to, że mam za dużo piosenek Johna, ale lista odtwarzania ma ponad 7000 linii i wygląda na to, jak sortzostała zaprojektowana.
Teresa e Junior
1
Jeśli chodzi o wydajność, shuftasuje listę odtwarzania 80 razy szybciej niż sort -R. Ja też tego nie wiedziałem! Pozostawię na 15 minut shuf, szanse są większe!
Teresa e Junior
Aby debugować, echo "$D"przed if. Powinno to powiedzieć, które duplikaty uniemożliwiły wybór wyniku. To powinno ci powiedzieć, gdzie szukać problemu. (Edycja: Dodano możliwy kod debugowania do odpowiedzi.)
frostschutz
DEBUG zawsze pokazuje około 100 linii, ale od przypadkowych artystów, więc wydaje się, że wielu artystów powoduje problem. Myślę, że tak naprawdę nie jest to możliwe przy pomocy sortlub shuf.
Teresa e Junior
1

Kolejne podejście przy użyciu Bash. Odczytuje listę odtwarzania w losowej kolejności, próbuje wstawić linię na drugim końcu listy, jeśli jest to duplikat, i odkłada pojedynczy duplikat, aby wstawić go w innym miejscu. Nie powiedzie się, jeśli istnieją potrójne duplikaty (pierwszy, ostatni i odłożone identycznie) i dołączą te złe wpisy na samym końcu listy. Wygląda na to, że jest w stanie rozwiązać obszerną listę, którą przesłałeś przez większość czasu.

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

Może być mądrzejszy ... w twoim przykładzie Johna, John zwykle będzie trwać przy byciu last_artist, ponieważ zawsze próbuje najpierw dołączyć first_artist. Więc jeśli dostanie dwóch innych artystów pomiędzy, nie jest wystarczająco mądry, aby dołączyć jednego na początku, a drugiego do końca, aby uniknąć potrójnego Johna. Tak więc z listami, które zasadniczo wymagają, aby każdy inny artysta był Johnem, masz więcej niepowodzeń niż powinieneś.

frostschutz
źródło
Dziękuję za ten skrypt bash. To jedyny, który mogę naprawdę zrozumieć i modyfikować do woli!
Teresa e Junior