Acak file secara acak dengan beberapa kendala tambahan

Saya memiliki daftar putar musik yang sangat besar dan, sementara beberapa artis memiliki banyak album, yang lain hanya memiliki satu lagu. Saya ingin mengurutkan daftar putar sehingga artis yang sama tidak akan bermain dua kali berturut-turut, atau lagu-lagunya sebagian besar tidak akan berakhir di awal atau akhir daftar putar.

Contoh daftar putar:

$ 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

Output dari sort -Ratau 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.

Apa yang saya harapkan:

$ 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

Jika saya harus menerapkan pengocokan tersebut ke setumpuk kartu remi, saya pikir saya pertama-tama akan mengocoknya, kemudian menampilkan kartu-kartu tersebut secara beruntun di depan mata saya dan memproses dari kiri ke kanan, di mana pun ada klub atau hati yang berdekatan .. Pindahkan semua kecuali satu dari mereka secara acak di tempat lain (meskipun tidak di sebelah yang lain dari jenis yang sama).

Misalnya dengan tangan suka

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

Setelah pengocokan dasar:

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

dua kelompok sekop yang berdekatan, kita perlu pindah 1, 2 dan 3. Untuk 1, pilihannya adalah:

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

Kami memilih satu secara acak dari 4. Itu. Kemudian kami ulangi proses untuk 2 dan 3.

Diimplementasikan dalam perlhal itu adalah:

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'

Ini akan menemukan solusi dengan artis yang tidak berdekatan jika ada (kecuali lebih dari setengah lagu dari artis yang sama), dan harus seragam AFAICT.

Contoh data dan batasan Anda sebenarnya hanya memungkinkan beberapa solusi — Anda harus memainkan John B. setiap lagu lainnya, misalnya. Saya akan menganggap daftar putar lengkap Anda yang sebenarnya pada dasarnya bukan John B, dengan hal-hal acak lainnya untuk dipecah .

Ini adalah pendekatan acak lain. Tidak seperti solusi @ frostschutz, ini berjalan dengan cepat. Namun, itu tidak menjamin hasil yang cocok dengan kriteria Anda. Saya juga menyajikan pendekatan kedua, yang bekerja pada data contoh Anda — tetapi saya curiga akan menghasilkan hasil yang buruk pada data Anda yang sebenarnya. Memiliki data asli Anda (dikaburkan), saya menambahkan pendekatan 3 — yang merupakan acak seragam, kecuali itu menghindari dua lagu oleh artis yang sama berturut-turut. Perhatikan bahwa itu hanya membuat 5 "menarik" ke dalam "dek" dari lagu yang tersisa, jika setelah itu masih dihadapkan dengan artis duplikat, itu akan tetap menghasilkan lagu itu — dengan cara ini, dijamin bahwa program akan benar-benar selesai.

Pendekatan 1

Pada dasarnya, ini menghasilkan daftar putar pada setiap titik, menanyakan "dari artis mana saya masih memiliki lagu yang belum diputar?" Kemudian memilih artis acak, dan akhirnya lagu acak dari artis itu. (Artinya, masing-masing artis diberi bobot yang sama, tidak sebanding dengan jumlah lagu.)

Cobalah daftar putar Anda yang sebenarnya, dan lihat apakah itu menghasilkan hasil yang lebih baik daripada acak yang seragam.

Penggunaan:./script-file < input.m3u > output.m3u Pastikan untuk chmod +xitu, tentu saja. Catatan itu tidak menangani garis tanda tangan yang ada di bagian atas beberapa file M3U dengan benar ... tetapi contoh Anda tidak memilikinya.

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

Pendekatan 2

Sebagai pendekatan kedua, alih-alih memilih artis acak , Anda dapat menggunakan memilih artis dengan lagu terbanyak, yang juga bukan artis terakhir yang kami pilih . Paragraf akhir program kemudian menjadi:

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

Sisa program tetap sama. Perhatikan bahwa ini sejauh ini bukan cara yang paling efisien untuk melakukan ini, tetapi harus cukup cepat untuk daftar putar dengan ukuran waras apa pun. Dengan data contoh Anda, semua daftar putar yang dihasilkan akan mulai dengan lagu John B., kemudian lagu Anna A., lalu lagu John B. Setelah itu, itu jauh lebih mudah diprediksi (karena semua orang kecuali John B. memiliki satu lagu yang tersisa). Perhatikan bahwa ini mengasumsikan Perl 5.7 atau lebih baru.

Pendekatan 3

Penggunaannya sama dengan 2. sebelumnya. Perhatikan 0..4bagiannya, dari situlah 5 mencoba maks berasal. Anda dapat meningkatkan jumlah percobaan, misalnya, 0..9akan memberikan 10 total. ( 0..4= 0, 1, 2, 3, 4, yang akan Anda perhatikan sebenarnya adalah 5 item).

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

Jika Anda tidak keberatan itu menjadi sangat tidak efisien ...

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"

Itu hanya terus bergulir dan bergulir sampai tiba pada hasil yang tidak memiliki dua atau lebih Johns berturut-turut. Jika ada begitu banyak John di daftar putar Anda sehingga kombinasi seperti itu tidak ada atau sangat tidak mungkin untuk digulirkan, yah, itu akan menggantung.

Contoh hasil dengan input Anda:

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

Jika Anda menghapus tanda komentar pada garis debug, itu akan memberi tahu Anda mengapa gagal:

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

Itu akan membantu menentukan penyebabnya jika ia hang tanpa batas.

Pendekatan lain menggunakan Bash. Bunyinya daftar putar dalam urutan acak, mencoba untuk memasukkan baris di ujung daftar lain jika itu adalah duplikat, dan menempatkan satu dupe samping untuk memasukkannya kembali di tempat lain. Gagal jika ada duplikat rangkap tiga (pertama, terakhir, dan disisihkan identik) dan itu akan menambahkan entri buruk itu ke bagian paling akhir daftar. Tampaknya dapat menyelesaikan daftar ekstensif yang Anda unggah sebagian besar waktu.

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

Bisa jadi lebih pintar ... dalam contoh John Anda, John biasanya akan tetap menjadi yang terakhir_artis karena selalu mencoba untuk menambahkan yang pertama_artis dulu. Jadi jika ada dua artis lain di antaranya, itu tidak cukup pintar untuk menambahkan satu ke awal dan yang lainnya sampai akhir untuk menghindari triple-John. Jadi dengan daftar yang pada dasarnya mengharuskan setiap artis lain menjadi John, Anda mendapatkan lebih banyak kegagalan daripada yang seharusnya.