1

Quick-and-dirty schedule optimization. An example: I have 7 different songs I can practice. I have 30 minutes total practice time. And I can break that into 5 minute windows. So I could practice one song for 30 minutes, or 6 different songs for 5 each, or one for 25 minutes and one for 5 minutes,etc. Separately I have a utility function and will be able to calculate the optimum configuration.

I need to generate all the various practice allocations. I did something like this before, the "algorithm" was revolting -- I generated all the possible combinations of [0,5,10,15,20,25,30]^7 and then threw away all those rows which didn't sum to 30.

Gross, stupid method, I know. I've been trying to identify what this problem is mathematically, then I should be able to find an efficient algorithm to solve it in Python. Alas, I cannot describe this to google well enough to find it.

Can anyone advise this problem class or appropriate algorithm to solve?

================

I did a lousy job describing the problem. Let me try again:

I have a single 30 minute window to practice my music. I have seven different songs that I could practice during that 30 minute window. For each of the seven songs, I can practice between 0, 5, 10, .., 25, 30 minutes, but total combined practice time of all songs must be 30 minutes. I have some utility function that scores the different possible practice schedules.

user3556757
  • 3,469
  • 4
  • 30
  • 70

1 Answers1

0

edit: As Gassa pointed out, order doesn't seem to matter here. So if I'm understanding the question now, you want itertools.combinations_with_replacement([1,2,3,4,5,6,7], r=6)

old answer:

What you are looking for is all of the permutations (with replacement) of length 6 of [1,2,3,4,5,6,7] (your array of songs). In total, there should be 7^6=117649. Using the method described in this answer:

import itertools
x = [1,2,3,4,5,6,7]
print len([p for p in itertools.product(x, repeat=6)])
# prints 117649

This gives you all your possible schedulings - they're in a different format from what you described (i.e. you need to convert "123123" into "10 minutes of song 1, 10 minutes of songs 2, 10 minutes of song 3"), but the conversion is quick.

Community
  • 1
  • 1
Greg
  • 597
  • 1
  • 6
  • 16
  • 1
    This method generates a different object, so in the OP's sense, it generates some schedules more than once. For example, both your "123123" and "123231" translate to the same "10 minutes of song 1, 10 minutes of songs 2, 10 minutes of song 3" in OP's view. – Gassa Jun 21 '16 at 15:33
  • @Greg apologies, I did a crappy job describing the problem. Added a more clear description in the question body. – user3556757 Jun 22 '16 at 13:26
  • 1
    Does my answer help? And I'm still not completely clear on whether your utility function depends also on the order in which you practice your songs, or only on the length of time for which each song is practiced. – Greg Jun 22 '16 at 15:20