Решение проблемы с перестановкой и ограничением

Question

Оптимизация быстрого и грязного расписания. Пример: у меня есть 7 разных песен, которые я могу практиковать. У меня есть 30 минут общего времени тренировки. И я могу разбить это на 5-минутные окна. Таким образом, я мог практиковать одну песню в течение 30 минут или 6 разных песен по 5 штук, или по 25 минут и один за 5 минут и т. Д. Отдельно у меня есть функция утилиты и вы сможете рассчитать оптимальную конфигурацию.

Мне нужно сгенерировать все различные распределения практики. Я делал что-то подобное раньше, «алгоритм» был отвратительным - я породил все возможные комбинации [0,5,10,15,20,25,30]^7, а затем выбросил все те строки, которые не сумма до 30.

Гросс, глупый метод, я знаю. Я пытался определить, что эта проблема математически, тогда я должен был бы найти эффективный алгоритм для ее решения в Python. Увы, я не могу описать это достаточно хорошо, чтобы найти его.

Может ли кто-нибудь посоветовать этот класс проблем или соответствующий алгоритм решить?

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

Я сделал паршивую работу с описанием проблемы. Позвольте мне попробовать еще раз:

У меня есть одно 30-минутное окно, чтобы попрактиковаться в моей музыке. У меня есть семь разных песен, которые я мог бы практиковать в течение этого 30-минутного окна. Для каждой из семи песен я могу тренироваться между 0, 5, 10, .., 25, 30 минут, но общее время тренировки всех песен должно составлять 30 минут. У меня есть функция полезности, которая учитывает различные возможные графики практики.

Answer 1

изменить: Как указал Гасса, порядок здесь не имеет значения. Так что, если я понять вопрос сейчас, вы хотите itertools.combinations_with_replacement([1,2,3,4,5,6,7], r=6)

старый ответ:

Что вы ищете все перестановки (с заменой) длиной 6 [1,2,3 , 4,5,6,7] (ваш массив песен). Всего должно быть 7^6 = 117649. Используя метод, описанный в 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 

Это дает вам все ваши возможные диспетчеризации - они в формате, отличном от того, что вы описали (т.е. вам нужно преобразовать «123123» в «10 минут песни 1, 10 минут песен 2, 10 минут песни 3 "), но конверсия идет быстро.