How can I divide 24 music albums into 6 playlists such that the running time / length is as evenly distributed as possible?

Question

NOTE: I plan to implement this using Java, but any plain-English explanation of the steps needed in the logic is welcome and appreciated.

I'm trying to come up with a way to divide a group of 24 music albums/records into 6 playlists such that the lengths/running time all 6 playlists are as close to each other as possible.

I initially thought that maybe I could find all possible permutations of the problem and then work out a logic that will analyze which is the best division. I even created a thread to ask for help for it yesterday (I have 24 items that I need to separate into 6 sets of 4. What algorithm can I use to find all possible combinations?). However, when I got close to finding a solution, I realized that just finding all permutations of the problem will take incredibly long to run, so that approach seem impractical.

So I was wondering, is there a faster way to approach such a problem?

Given that these are the running times of the albums in question (in MM:SS format), what is the fastes way for me to find the division of albums into 6 playlists of 4 such that the lengths of each of the playlists is as close to each other as possible?

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 

I did the math and considering the total time for all the albums, having 6 playlists that run at 200 minutes and 49 seconds would be perfect... but since the individual album lengths probably don't allow for that exact of a division, what would be the most exact possible division is my question.

NOTE: I could actually do this manually and get a close enough approximation that would suffice, but I am still really interested on how it could be done through a program.

Thanks!

Answer 1

I'd suggest you to use a Simulated annealing algorithm

And here is one nice solution derived by this algorithm:

[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

As Steven Skiena pointed in his book ("The Algorithm Design Manual"), that it is very helpful to use Simulated annealing metaheuristic for finding acceptable solutions in real life combinatorial problems.

So, as you mentioned, you need to put 4 tracks in each of 6 albums such that all albums will have approximately the same duration.

Firstly lets consider - which property do we need to optimize?

From my point of view - the most suitable formulation would be: minimize standard deviation of durations of all albums. (But, if needed - you are free to include any other, more complex, properties).

Let's name the value of an optimized property as energy.

The main idea of algorithm

Each state of our system is characterized by some value of energy. By performing some actions over the system we can change its state (e.g. Swapping tracks between different albums).

Also, we have some abstract property called temperature.

When system is under high temperature, it is free to change its state to another state, even if the new state has a higher value of energy.

But when the temperature is small, the system tends to change its state mostly to new states with lower values of energy.

By physical analogy, the probability of changing the current state of system to a state with a higher value of energy can be limited in the same way as Boltzmann distribution defines.

Here is an illustration of how the standard deviation of durations changed while deriving the solution from above

Here is a full Java implementation of algorithm, which gives the solution from above

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

Answer 2

This is equivalent* to multiprocessor scheduling if you consider each album as a job and each playlist as a processor, and finding an optimal solution is NP-hard.

However, there are efficient algorithms which give decent but not necessarily optimal results. For example, sorting the albums by length and repeatedly adding the longest album to the shortest playlist.

If we number the albums from 1 to 24 from shortest to longest, this algorithm gives the following division.

{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)

* If we consider "evenly distributed" to mean that the length of the longest playlist is minimized.