Algorithm design, "randomising" timetable schedule in Python although open to other languages.

Question

Before I start I should add I am a musician and not a native programmer, this was undertook to make my life easier.

Here is the situation, at work I'm given a new csv file each which contains a list of sound files, their length, and the minimum total amount of time they must be played.

I create a playlist of exactly 60 minutes, from this excel file.

Each sample played the by the minimum number of instances, but spread out from each other; so there will never be a period where for where one sound is played twice in a row or in close proximity to itself.

Secondly, if the minimum instances of each song has been used, and there is still time with in the 60 min, it needs to fill the remaining time using sounds till 60 minutes is reached, while adhering to above.

The smallest duration possible is 15 seconds, and then multiples of 15 seconds.

---

Here is what I came up with in python and the problems I'm having with it, and as one user said its buggy due to the random library used in it.

So I'm guessing a total rethink is on the table, here is where I need your help.

Whats is the best way to solve the issue, I have had a brief look at things like knapsack and bin packing algorithms, while both are relevant neither are appropriate and maybe a bit beyond me.

Answer 1

Your problem is an interesting one. Strictly you can't solve it without an NP-complete search. This shouldn't be a big problem, if implemented nicely, for your size of problem space. NP-complete problems are renowned for being 'hard' in computer science terms, but for a small number of elements, they are easily tractable.

An algorithm such as A* will work nicely for you here. And will be (provably) optimal.

You could make it a fraction simpler by making a simplifying assumption and splitting the problem into two subproblems:

1. Given a list of objects, arrange the list so that no two sequential objects are the same. Strictly this is another NP-complete problem. But you will often be able to achieve this by a simple algorithm: starting with an empty list, insert the next sample at the first location in the list where it doesn't violate the ordering constraint. That simple algorithm will fail in some cases where there is a correct solution, but may be all you need.

2. Take the 60 minutes, subtract the running time of the minimum durations of all your samples, to be left with X minutes remaining. Your assignment of additional samples to reach your X minutes is discretionary. This is a classic knapsack problem.

The simplifying assumption is that you can do this decomposition. In practice the two problems interact: your choice in step 2 can influence how easy step 1 is, for example.

---

So if it were me, I'd implement a simple search system, such as A*. But if that algorithm seems to exotic and difficult to implement, try breaking the problem down as above.

Follow up with questions if I've been unclear.

Answer 2

I don't usually just write the whole program as an answer to a question but this one is just an interesting challenge in itself. So here is how I would do it:

samples1 = {'Soundfoo': (120, 10),
            'Soundbar': (30, 6),
            'Sounddev': (60, 20), 
            'Soundrandom': (15, 8)}

samples2 = {'Sound1': (60,10),
            'Sound2': (60,10),
            'Sound3': (60,10),
            'Sound4': (60,10),
            'Sound5': (60,10),
            'Sound6': (60,10)}

def create_playlist(samples):

    import random

    playlist = []
    for k, v in samples.iteritems():
        playlist.extend([k] * (v[1] * 60 / v[0]))

    shortest_sample = min(i[0] for i in samples.itervalues())
    remainder = 60 * 60 - sum(samples[i][0] for i in playlist)
    while remainder > 0:
        o = [k for k in samples.keys() if samples[k][0] <= remainder and
                remainder - samples[k][0] > shortest_sample]
        if len(o) == 0: break
        c = random.choice(o)
        playlist.append(c)
        remainder -= samples[c][0]

    random.shuffle(playlist)

    def is_random(p):
        for i in xrange(1, len(p)):
            if p[i] == p[i-1]: return i
        return True

    i = is_random(playlist)
    while i is not True:
        for j in xrange(i+1, i+len(playlist)-1):
            k = j % len(playlist)
            if playlist[k] != playlist[i]:
                playlist[i], playlist[k] = playlist[k], playlist[i]
                break
        i = is_random(playlist)

    return playlist

print create_playlist(samples1)
print create_playlist(samples2)

What this does is as follows:

1. Creates the initial value of playlist as each sample repeated continuously for as many times as minimally needed.
2. Fills the playlist with a random selection (random.choice()) of samples to get the length up to the needed 60 minutes. When choosing an item at random make sure that it would not make the remaining time too short for anything to fill.
3. Shuffles the playlist in place (random.shuffle())
4. Defines a function that checks for two identical samples being played one after the other.
5. Using the above function, find a repeated element, then move down the playlist (and loop around the beginning up to the repeated item) and look for a different sample. When one is found, switch it with the repeated sample. Rinse and repeat until there are no more repetitions.

The only problem I can think of it that this hangs if there is only one sample but I bet you can take care of that if such a case is possible.

I am sure there are more optimal solutions but given the small number of samples we are working with here, I think this will suffice. Besides, I have always believed there is something elegant about an that algorithm just does what a normal person would do given the same problem.