生成组合对象的算法

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)

我还没有机会测试任何此代码，因此可能需要一些调整。如果您需要严格的效率，请转换为非递归样式 - 然而，相对较低的性能增益可能不会对您当前的需求产生影响。