Алгоритм генерации комбинаторных объектов

Question

Я работаю над проектом генерации расписания, и мне нужно предварительно обработать данные, прежде чем поместить их в модель LP.

Мне нужно создать комбинаторные объекты для использования в оптимизации. Эта проблема очень похожа на проблему резки древесины.

Скажите, что у меня есть 3 класса {A, B, C} и 2 классных комнаты, у меня были бы следующие образцы:

A
AA
B
BB
C
CC
AB
AC
BC

Если бы у меня было 2 класса {A, B} и 3 классных комнаты, у меня были бы следующие образцы:

A
AA
AAA
B
BB
BBB
AB
ABB
AAB

3 занятия в 3 комнатах дадут:

A, B, C,
AA, AB, AC, BB, BC, CC,
AAA, AAB, AAC, ABB, ABC,
ACC, BBB, BBC, BCC, CCC

Мне нужен эффективный алгоритм, который генерирует эти шаблоны. Мои действительные числа больше похожи на 5+ классных комнат и 30+ классов, но алгоритм должен уметь обрабатывать и гораздо большие числа.

Answer 1

если вы используете python, вы можете использовать что-то вроде:

import itertools
import pprint

def f(classes,classrooms):
    print classes,classrooms
    classes="ABCDEFGHIJKLMNOPQRSTUVWXYZ"[:classes]
    for i in range(1,classrooms+1):
        combinations=itertools.combinations_with_replacement(classes,i)
        pprint.pprint(["".join(j) for j in combinations])

f(3,2)

f(2,3)

f(3,3)

>>>
3 2
['A', 'B', 'C']
['AA', 'AB', 'AC', 'BB', 'BC', 'CC']
2 3
['A', 'B']
['AA', 'AB', 'BB']
['AAA', 'AAB', 'ABB', 'BBB']
3 3
['A', 'B', 'C']
['AA', 'AB', 'AC', 'BB', 'BC', 'CC']
['AAA', 'AAB', 'AAC', 'ABB', 'ABC', 'ACC', 'BBB', 'BBC', 'BCC', 'CCC']
>>>

Answer 2

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

Базовый алгоритм в C # -подобном синтаксисе выглядит следующим образом:

void GenerateCombinations(string comboSoFar, string classLetters, int level, int maxLevel)
{
    foreach (char letter in classLetters)
    {
        comboSoFar = comboSoFar + letter.ToString();
        Console.WriteLine(comboSoFar);
        if (level < maxLevel)
            GenerateCombinations(comboSoFar, classLetters, level + 1, maxLevel)
    }
}

И запустите рекурсивную функцию с вашей базовой линией:

GenerateCombinations("", "ABCD", 1, numberOfClassrooms)

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