Как я могу разделить 24 музыкальных альбома на 6 плейлистов, так что время/длина работы равномерно распределены по возможности?

Ответ 1

Я предлагаю вам использовать алгоритм имитированного отжига

И вот одно приятное решение, полученное с помощью этого алгоритма:

[17, 16, 15, 9] 199:39
[3, 14, 10, 24] 199:50
[6, 8, 13, 21]  199:52
[1, 5, 20, 19]  199:55
[4, 23, 2, 18]  199:47
[11, 7, 22, 12] 199:51

Как Стивен Скиена указал в своей книге ( "Руководство по разработке алгоритмов" ), что очень полезно использовать Имитированный отжиг метаэвристический для нахождения приемлемых решений в комбинаторных задачах реальной жизни.

Итак, как вы уже упоминали, вам нужно поставить 4 трека в каждом из 6 альбомов, чтобы все альбомы имели примерно такую ​​же продолжительность.

Во-первых, рассмотрим - какое свойство нам нужно оптимизировать?

С моей точки зрения, наиболее подходящей формулировкой было бы: минимизировать стандартное отклонение продолжительности всех альбомов. (Но при необходимости - вы можете включать любые другие, более сложные свойства).

Назовите значение оптимизированного свойства как Энергия.

Основная идея алгоритма

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

Кроме того, у нас есть некоторое абстрактное свойство, называемое температура.

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

Но когда температура мала, система имеет тенденцию менять свое состояние в основном на новые состояния с более низкими значениями энергии.

По физической аналогии вероятность изменения текущего состояния системы в состоянии с более высоким значением энергии может быть ограничена так же, как Boltzmann распространение.

Вот иллюстрация того, как стандартное отклонение длительностей изменилось при выводе решения сверху

Вот полная реализация алгоритма Java, которая дает решение сверху

import java.util.Arrays;
import java.util.Random;

public class SimulatedAnnealingTracksOrdering {

    public static void main(String[] args) {
        int albumsCount = 6;
        int tracksInAlbum = 4;

        Album[] result = generateOptimalTracksOrdering(
                tracksInAlbum,
                albumsCount,
                new Track[] {
                        new Track(1, "39:03"), new Track(2, "41:08"),
                        new Track(3, "41:39"), new Track(4, "42:54"),
                        new Track(5, "44:31"), new Track(6, "44:34"),
                        new Track(7, "44:40"), new Track(8, "45:55"),
                        new Track(9, "45:59"), new Track(10, "47:06"),
                        new Track(11, "47:20"), new Track(12, "47:53"),
                        new Track(13, "49:35"), new Track(14, "49:57"),
                        new Track(15, "50:15"), new Track(16, "51:35"),
                        new Track(17, "51:50"), new Track(18, "55:45"),
                        new Track(19, "58:10"), new Track(20, "58:11"),
                        new Track(21, "59:48"), new Track(22, "59:58"),
                        new Track(23, "60:00"), new Track(24, "61:08"),
                });

        for (Album album : result) {
            System.out.println(album);
        }
    }

    private static Album[] generateOptimalTracksOrdering(
            int tracksInAlbum, int albumsCount, Track[] tracks) {

        // Initialize current solution
        Albums currentSolution =
                new Albums(tracksInAlbum, albumsCount, tracks);
        // Initialize energy of a current solution
        double currentEnergy =
                currentSolution.albumsDurationStandartDeviation();

        System.out.println("Current energy is: " + currentEnergy);

        // Also, we will memorize the solution with smallest value of energy
        Albums bestSolution = currentSolution.clone();
        double bestEnergy = currentEnergy;

        // Constant, which defines the minimal value of energy
        double minEnergy = 0.1;
        // Initial temperature
        double temperature = 150;
        // We will decrease value of temperature, by multiplying on this
        // coefficient
        double alpha = 0.999;
        // Constant, which defines minimal value of temperature
        double minTemperature = 0.1;
        // For each value of temperature - we will perform few probes, before
        // decreasing temperature
        int numberOfProbes = 100;

        Random random = new Random(1);

        while ((temperature > minTemperature)
                && (currentEnergy > minEnergy)) {

            for (int i = 0; i < numberOfProbes; i++) {
                // Generating new state
                currentSolution.randomTracksPermutation();
                double newEnergy =
                        currentSolution.albumsDurationStandartDeviation();

                // As defined by Boltzmann distribution
                double acceptanceProbability = 
                        Math.exp(-(newEnergy - currentEnergy) / temperature);

                // States with smaller energy - will be accepted always
                if ((newEnergy < currentEnergy)
                        || (random.nextDouble() < acceptanceProbability)) {

                    currentEnergy = newEnergy;
                    System.out.println("Current energy is: " + currentEnergy);

                    if (newEnergy < bestEnergy) {
                        bestSolution = currentSolution.clone();
                        bestEnergy = newEnergy;
                    }
                } else {
                    // If state can't be accepted - rollback to previous state
                    currentSolution.undoLastPermutation();
                }
            }
            // Decreasing temperature
            temperature *= alpha;
        }
        // Return best solution
        return bestSolution.getAlbums();
    }
}

/**
 * Container for bunch of albums
 */
class Albums {
    private Random random = new Random(1);
    private Album[] albums;
    // These fields, are used for memorizing last permutation
    // (needed for rollbacking)
    private Album sourceAlbum;
    private int sourceIndex;
    private Album targetAlbum;
    private int targetIndex;

    public Albums(int tracksInAlbum, int albumsCount, Track[] tracks) {
        // Put all tracks to albums
        this.albums = new Album[albumsCount];
        int t = 0;
        for (int i = 0; i < albumsCount; i++) {
            this.albums[i] = new Album(tracksInAlbum);
            for (int j = 0; j < tracksInAlbum; j++) {
                this.albums[i].set(j, tracks[t]);
                t++;
            }
        }
    }

    /**
     * Calculating standard deviations of albums durations
     */
    public double albumsDurationStandartDeviation() {
        double sumDuration = 0;
        for (Album album : this.albums) {
            sumDuration += album.getDuraion();
        }
        double meanDuration =
                sumDuration / this.albums.length;

        double sumSquareDeviation = 0;
        for (Album album : this.albums) {
            sumSquareDeviation +=
                    Math.pow(album.getDuraion() - meanDuration, 2);
        }
        return Math.sqrt(sumSquareDeviation / this.albums.length);
    }

    /**
     * Performing swapping of random tracks between random albums
     */
    public void randomTracksPermutation() {
        this.sourceAlbum = this.pickRandomAlbum();
        this.sourceIndex =
                this.random.nextInt(this.sourceAlbum.getTracksCount());

        this.targetAlbum = this.pickRandomAlbum();
        this.targetIndex =
                this.random.nextInt(this.targetAlbum.getTracksCount());

        this.swapTracks();
    }

    public void undoLastPermutation() {
        this.swapTracks();
    }

    private void swapTracks() {
        Track sourceTrack = this.sourceAlbum.get(this.sourceIndex);
        Track targetTrack = this.targetAlbum.get(this.targetIndex);

        this.sourceAlbum.set(this.sourceIndex, targetTrack);
        this.targetAlbum.set(this.targetIndex, sourceTrack);
    }

    private Album pickRandomAlbum() {
        int index = this.random.nextInt(this.albums.length);
        return this.albums[index];
    }

    public Album[] getAlbums() {
        return this.albums;
    }

    private Albums() {
        // Needed for clonning
    }

    @Override
    protected Albums clone() {
        Albums cloned = new Albums();
        cloned.albums = new Album[this.albums.length];
        for (int i = 0; i < this.albums.length; i++) {
            cloned.albums[i] = this.albums[i].clone();
        }
        return cloned;
    }
}

/**
 * Container for tracks
 */
class Album {
    private Track[] tracks;

    public Album(int size) {
        this.tracks = new Track[size];
    }

    /**
     * Duration of album == sum of durations of tracks
     */
    public int getDuraion() {
        int acc = 0;
        for (Track track : this.tracks) {
            acc += track.getDuration();
        }
        return acc;
    }

    public Track get(int trackNum) {
        return this.tracks[trackNum];
    }

    public void set(int trackNum, Track track) {
        this.tracks[trackNum] = track;
    }

    public int getTracksCount() {
        return this.tracks.length;
    }

    public Track[] getTracks() {
        return this.tracks;
    }

    @Override
    protected Album clone() {
        Album cloned = new Album(this.tracks.length);
        for (int i = 0; i < this.tracks.length; i++) {
            cloned.tracks[i] = this.tracks[i];
        }
        return cloned;
    }

    /**
     * Displaying duration in MM:SS format
     */
    @Override
    public String toString() {
        int duraion = this.getDuraion();
        String duration_MM_SS = (duraion / 60) + ":" + (duraion % 60);
        return Arrays.toString(this.tracks) + "\t" + duration_MM_SS;
    }

}

class Track {
    private final int id;
    private final int durationInSeconds;

    public Track(int id, String duration_MM_SS) {
        this.id = id;
        this.durationInSeconds =
                this.parseDuration(duration_MM_SS);
    }

    /**
     * Converting MM:SS duration to seconds
     */
    private int parseDuration(String duration_MM_SS) {
        String[] parts = duration_MM_SS.split(":");
        return (Integer.parseInt(parts[0]) * 60)
                + Integer.parseInt(parts[1]);
    }

    public int getDuration() {
        return this.durationInSeconds;
    }

    public int getId() {
        return this.id;
    }

    @Override
    public String toString() {
        return Integer.toString(this.id);
    }
}

Ответ 2

Это эквивалентно * многопроцессорному планированию, если вы рассматриваете каждый альбом как задание и каждый плейлист как процессор, а поиск оптимального решения - NP-hard.

Однако существуют эффективные алгоритмы, которые дают достойные, но не обязательно оптимальные результаты. Например, сортировка альбомов по длине и повторное добавление самого длинного альбома в самый короткий список воспроизведения.

Если мы будем отбирать альбомы от 1 до 24 от самого короткого до самого длинного, этот алгоритм дает следующее деление.

{24, 13,  9,  6}  (201:16)
{23, 14, 12,  2}  (198:58)
{22, 15, 10,  4}  (200:13)
{21, 16,  8,  5}  (201:49)
{20, 17, 11,  3}  (199:00)
{19, 18,  7,  1}  (197:38)

* Если мы считаем "равномерно распределенным" означать, что длина самого длинного списка воспроизведения сводится к минимуму.

Ответ 3

С более интеллектуальным алгоритмом поиска, чем грубая сила, нам не нужно проходить все возможности 1e12. Сначала мы преобразуем входные данные, перечислим все четыре набора и отсортируем их по их близости к целевому времени.

import heapq
import itertools
import re

def secondsfromstring(s):
    minutes, seconds = s.split(':')
    return int(minutes) * 60 + int(seconds)

def stringfromseconds(seconds):
    minutes, seconds = divmod(seconds, 60)
    return '{}:{:02}'.format(minutes, seconds)

# for simplicity, these have to be pairwise distinct
stringtimes = '''39:03 41:08 41:39 42:54 44:31 44:34
                 44:40 45:55 45:59 47:06 47:20 47:53
                 49:35 49:57 50:15 51:35 51:50 55:45
                 58:10 58:11 59:48 59:58 60:00 61:08'''
times = [secondsfromstring(s) for s in stringtimes.split()]
quads = [frozenset(quad) for quad in itertools.combinations(times, 4)]
targettime = sum(times) / 6
quads.sort(key=lambda quad: abs(sum(quad) - targettime))

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

queue = [(0, frozenset(times), [])]
while True:
    i, remaining, sofar = heapq.heappop(queue)
    if not remaining:
        for quad in sofar:
            print(stringfromseconds(sum(quad)), ':',
                  *(stringfromseconds(time) for time in quad))
        break
    while i < len(quads):
        quad = quads[i]
        if quad.issubset(remaining):
            heapq.heappush(queue, (i + 1, remaining, sofar))
            heapq.heappush(queue, (i + 1, remaining - quad, sofar + [quad]))
            break
        i += 1

Через пару секунд этот код высветит следующий оптимальный ответ. (Нам повезло, так как этот код работает над слегка измененной целью минимизации максимального отклонения от целевого времени, а с более сложной программой ниже мы можем минимизировать разницу между минимумом и максимумом, которая оказывается той же группировкой.)

199:50 : 47:06 41:39 61:08 49:57
199:52 : 44:34 45:55 59:48 49:35
199:45 : 55:45 41:08 59:58 42:54
199:53 : 44:40 47:20 60:00 47:53
199:55 : 58:10 44:31 58:11 39:03
199:39 : 51:35 50:15 51:50 45:59

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

import heapq
import itertools
import re

def secondsfromstring(s):
    minutes, seconds = s.split(':')
    return int(minutes) * 60 + int(seconds)

def stringfromseconds(seconds):
    minutes, seconds = divmod(seconds, 60)
    return '{}:{:02}'.format(minutes, seconds)

# for simplicity, these have to be pairwise distinct
stringtimes = '''39:03 41:08 41:39 42:54 44:31 44:34
                 44:40 45:55 45:59 47:06 47:20 47:53
                 49:35 49:57 50:15 51:35 51:50 55:45
                 58:10 58:11 59:48 59:58 60:00 61:08'''
times = [secondsfromstring(s) for s in stringtimes.split()]
quads = [frozenset(quad) for quad in itertools.combinations(times, 4)]
targettime = sum(times) / 6
quads.sort(key=lambda quad: abs(sum(quad) - targettime))

def span(solution):
    quadtimes = [sum(quad) for quad in solution]
    return max(quadtimes) - min(quadtimes)

candidates = []
bound = None
queue = [(0, frozenset(times), [])]
while True:
    i, remaining, sofar = heapq.heappop(queue)
    if not remaining:
        candidates.append(sofar)
        newbound = span(sofar)
        if bound is None or newbound < bound: bound = newbound
    if bound is not None and abs(sum(quads[i]) - targettime) >= bound: break
    while i < len(quads):
        quad = quads[i]
        i += 1
        if quad.issubset(remaining):
            heapq.heappush(queue, (i, remaining, sofar))
            heapq.heappush(queue, (i, remaining - quad, sofar + [quad]))
            break
best = min(candidates, key=span)
for quad in best:
    print(stringfromseconds(sum(quad)), ':',
          *(stringfromseconds(time) for time in quad))

Ответ 4

Это тоже комментарий, но он слишком длинный, поэтому я отправляю его как ответ. Это небольшое упрощение кода для решения hammar. Этот алгоритм не дает вам оптимального решения, но он находит лучшее.

Вы можете начать с hammar жадного алгоритма, чтобы заполнить плейлисты альбомами. Дальше все, что вам нужно сделать, это перебирать их несколько раз. Пусть D разность между общей длиной списка воспроизведения A и списком воспроизведения B, где length(A)>length(B). Прокрутите плейлисты A и B, и если вы найдете альбомы x \in A и y \in B, которые соответствуют x>y && x-y<D, замените x и y.
Это дало мне следующие результаты:

{7,8,22,13}   200:8
{2,11,24,15}  199:51
{4,10,23,14}  199:57
{3,17,12,19}  199:32
{5,16,21,6}   200:28
{1,18,9,20}   198:58

Ответ 5

Для чего стоит, прежде чем stemm разместил свой алгоритм имитированного отжига, у меня уже было решение, которое приблизилось к тому, что я искал. Итак, просто чтобы поделиться другим (хотя и относительно грубым) подходом, вот он:

(1) Я отсортировал все индивидуальные длительности треков от самого короткого до самого длинного.

#01 - 39:03 
#02 - 41:08 
#03 - 41:39 
#04 - 42:54 
#05 - 44:31 
#06 - 44:34 
#07 - 44:40 
#08 - 45:55 
#09 - 45:59 
#10 - 47:06 
#11 - 47:20 
#12 - 47:53 
#13 - 49:35 
#14 - 49:57 
#15 - 50:15 
#16 - 51:35 
#17 - 51:50 
#18 - 55:45
#19 - 58:10 
#20 - 58:11 
#21 - 59:48 
#22 - 59:58   
#23 - 60:00 
#24 - 61:08 

(2) Я сгруппирован в группы из 4 таких, что результирующие плейлисты теоретически имеют на короткое расстояние друг от друга только на основе их позиций в отсортированном списке, и эта группировка будет: самый короткий предмет + самый длинный элемент + средние два элемента... затем из оставшегося (все еще отсортированного) списка, снова самый короткий + самый длинный + средний два элемента... так далее и т.д., пока все элементы не будут сгруппированы вместе.

(3) Используя результирующие наборы из 4 теперь, я повторяю все отдельные альбомы в каждом из наборов, заменяя каждый элемент для каждого другого элемента из других наборов. Если при их замене расстояние от их исходных наборов становится меньше, тогда совершите обмен. Остальное, пропустите своп. Затем я просто делал это несколько раз, пока два альбома не могут меняться местами, чтобы уменьшить расстояние между родительскими наборами.

Чтобы проиллюстрировать шаг №3 в коде:

Partitioner(){
    for(int i=0;i<total.length;i++)
        total[i] = 0;

    // get the total time for all sets of four albums
    for(int i=0;i<sets.length;i++){
        for(int j=0;j<sets[i].length;j++){
            total[i] = total[i] + sets[i][j];
        }
    }

    // this method will be called recursively until no more swaps can be done
    swapper();

    for(int i=0;i<sets.length;i++){
        for(int j=0;j<sets[i].length;j++){
            System.out.println(sets[i][j]);
        }
    }
}

void swapper(){
    int count = 0;  

    for(int i=0;i<sets.length;i++){ // loop through all the sets
        for(int j=0;j<sets[i].length;j++){ // loop through all the album in a set
            for(int k=0;k<sets.length;k++){ // for every album, loop through all the other sets for comparison
                if(k!=i){ // but of course, don't compare it to its own set
                    for(int l=0;l<sets[k].length;l++){ // pair the album (sets[i][j]) with every album from the other sets
                        int parentA = total[i]; // store the total length from the parent set of album sets[i][j] 
                        int parentB = total[k]; // store the total length from the parent set of the album being compared
                        int origDist = Math.abs(parentA - parentB); // measure the original distance between those two sets
                        int newA = total[i] - sets[i][j] + sets[k][l]; //compute new length of "parentA" if the two albums were swapped
                        int newB = total[k] - sets[k][l] + sets[i][j]; //compute new length of "parentB" if the two albums were swapped
                        int newdist = Math.abs(newA - newB); //compute new distance if the two albums were swapped
                        if(newdist<origDist){ // if the new resulting distance is less than the original distance, commit the swap
                            int temp = sets[i][j];
                            sets[i][j] = sets[k][l];
                            sets[k][l] = temp;
                            total[i] = newA;
                            total[k] = newB;
                            count++;

                        }
                    }
                }
            }
        }
    }
    System.out.println(count);
    if (count > 0 ){
        swapper();
    }
}