Как оптимизировать перебор
Я перебираю все возможные варианты комбинаций. У меня получился вот такой код:
private void generate_Click(object sender, RoutedEventArgs e)
{
schedules = new List<Schedule>();
foreach(Form form in forms)
{
List<Schedule> variations = new List<Schedule>();
List<Lesson>[] lessonVariations = new List<Lesson>[36];
int id = 0;
for(int i1 = 0; i1 < form.lessons.Count; i1++)
for (int i2 = 0; i2 < form.lessons.Count; i2++)
for (int i3 = 0; i3 < form.lessons.Count; i3++)
for (int i4 = 0; i4 < form.lessons.Count; i4++)
for (int i5 = 0; i5 < form.lessons.Count; i5++)
for (int i6 = 0; i6 < form.lessons.Count; i6++)
for (int i7 = 0; i7 < form.lessons.Count; i7++)
for (int i8 = 0; i8 < form.lessons.Count; i8++)
for (int i9 = 0; i9 < form.lessons.Count; i9++)
for (int i10 = 0; i10 < form.lessons.Count; i10++)
for (int i11 = 0; i11 < form.lessons.Count; i11++)
for (int i12 = 0; i12 < form.lessons.Count; i12++)
for (int i13 = 0; i13 < form.lessons.Count; i13++)
for (int i14 = 0; i14 < form.lessons.Count; i14++)
for (int i15 = 0; i15 < form.lessons.Count; i15++)
for (int i16 = 0; i16 < form.lessons.Count; i16++)
for (int i17 = 0; i17 < form.lessons.Count; i17++)
for (int i18 = 0; i18 < form.lessons.Count; i18++)
for (int i19 = 0; i19 < form.lessons.Count; i19++)
for (int i20 = 0; i20 < form.lessons.Count; i20++)
for (int i21 = 0; i21 < form.lessons.Count; i21++)
for (int i22 = 0; i22 < form.lessons.Count; i22++)
for (int i23 = 0; i23 < form.lessons.Count; i23++)
for (int i24 = 0; i24 < form.lessons.Count; i24++)
for (int i25 = 0; i25 < form.lessons.Count; i25++)
for (int i26 = 0; i26 < form.lessons.Count; i26++)
for (int i27 = 0; i27 < form.lessons.Count; i27++)
for (int i28 = 0; i28 < form.lessons.Count; i28++)
for (int i29 = 0; i29 < form.lessons.Count; i29++)
for (int i30 = 0; i30 < form.lessons.Count; i30++)
for (int i31 = 0; i31 < form.lessons.Count; i31++)
for (int i32 = 0; i32 < form.lessons.Count; i32++)
for (int i33 = 0; i33 < form.lessons.Count; i33++)
for (int i34 = 0; i34 < form.lessons.Count; i34++)
for (int i35 = 0; i35 < form.lessons.Count; i35++)
for (int i36 = 0; i36 < form.lessons.Count; i36++)
{
variations.Add(new Schedule());
variations[id].days[0].lessons[0] = form.lessons[i1];
variations[id].days[0].lessons[1] = form.lessons[i2];
variations[id].days[0].lessons[2] = form.lessons[i3];
variations[id].days[0].lessons[3] = form.lessons[i4];
variations[id].days[0].lessons[4] = form.lessons[i5];
variations[id].days[0].lessons[5] = form.lessons[i6];
variations[id].days[1].lessons[0] = form.lessons[i7];
variations[id].days[1].lessons[1] = form.lessons[i8];
variations[id].days[1].lessons[2] = form.lessons[i9];
variations[id].days[1].lessons[3] = form.lessons[i10];
variations[id].days[1].lessons[4] = form.lessons[i11];
variations[id].days[1].lessons[5] = form.lessons[i12];
variations[id].days[2].lessons[0] = form.lessons[i13];
variations[id].days[2].lessons[1] = form.lessons[i14];
variations[id].days[2].lessons[2] = form.lessons[i15];
variations[id].days[2].lessons[3] = form.lessons[i16];
variations[id].days[2].lessons[4] = form.lessons[i17];
variations[id].days[2].lessons[5] = form.lessons[i18];
variations[id].days[3].lessons[0] = form.lessons[i19];
variations[id].days[3].lessons[1] = form.lessons[i20];
variations[id].days[3].lessons[2] = form.lessons[i21];
variations[id].days[3].lessons[3] = form.lessons[i22];
variations[id].days[3].lessons[4] = form.lessons[i23];
variations[id].days[3].lessons[5] = form.lessons[i24];
variations[id].days[4].lessons[0] = form.lessons[i25];
variations[id].days[4].lessons[1] = form.lessons[i26];
variations[id].days[4].lessons[2] = form.lessons[i27];
variations[id].days[4].lessons[3] = form.lessons[i28];
variations[id].days[4].lessons[4] = form.lessons[i29];
variations[id].days[4].lessons[5] = form.lessons[i30];
variations[id].days[5].lessons[0] = form.lessons[i31];
variations[id].days[5].lessons[1] = form.lessons[i32];
variations[id].days[5].lessons[2] = form.lessons[i33];
variations[id].days[5].lessons[3] = form.lessons[i34];
variations[id].days[5].lessons[4] = form.lessons[i35];
variations[id].days[5].lessons[5] = form.lessons[i36];
id++;
}
}
}
Абсолютно полностью уверен, что это далеко не самое лучшее использование возможностей с#. Чтобы не засорять память я буду сразу проверять подходит ли нам такая комбинация, но как это более умно оформить?
Ответы (2 шт):
Автор решения: EvgeniyZ
→ Ссылка
У вас изначально код имеет довольно странную архитектуру, давайте немного разберем.
variations.Add(new Schedule());
variations[id].days[0].lessons[0] = form.lessons[i1];
variations[id].days[0].lessons[1] = form.lessons[i2];
variations[id].days[0].lessons[2] = form.lessons[i3];
variations[id].days[0].lessons[3] = form.lessons[i4];
variations[id].days[0].lessons[4] = form.lessons[i5];
variations[id].days[0].lessons[5] = form.lessons[i6];
variations[id].days[1].lessons[0] = form.lessons[i7];
variations[id].days[1].lessons[1] = form.lessons[i8];
variations[id].days[1].lessons[2] = form.lessons[i9];
variations[id].days[1].lessons[3] = form.lessons[i10];
variations[id].days[1].lessons[4] = form.lessons[i11];
variations[id].days[1].lessons[5] = form.lessons[i12];
variations[id].days[2].lessons[0] = form.lessons[i13];
variations[id].days[2].lessons[1] = form.lessons[i14];
variations[id].days[2].lessons[2] = form.lessons[i15];
variations[id].days[2].lessons[3] = form.lessons[i16];
variations[id].days[2].lessons[4] = form.lessons[i17];
variations[id].days[2].lessons[5] = form.lessons[i18];
variations[id].days[3].lessons[0] = form.lessons[i19];
variations[id].days[3].lessons[1] = form.lessons[i20];
variations[id].days[3].lessons[2] = form.lessons[i21];
variations[id].days[3].lessons[3] = form.lessons[i22];
variations[id].days[3].lessons[4] = form.lessons[i23];
variations[id].days[3].lessons[5] = form.lessons[i24];
variations[id].days[4].lessons[0] = form.lessons[i25];
variations[id].days[4].lessons[1] = form.lessons[i26];
variations[id].days[4].lessons[2] = form.lessons[i27];
variations[id].days[4].lessons[3] = form.lessons[i28];
variations[id].days[4].lessons[4] = form.lessons[i29];
variations[id].days[4].lessons[5] = form.lessons[i30];
variations[id].days[5].lessons[0] = form.lessons[i31];
variations[id].days[5].lessons[1] = form.lessons[i32];
variations[id].days[5].lessons[2] = form.lessons[i33];
variations[id].days[5].lessons[3] = form.lessons[i34];
variations[id].days[5].lessons[4] = form.lessons[i35];
variations[id].days[5].lessons[5] = form.lessons[i36];
Что мы тут имеем?
Создание пустого объекта и дальнейший поиск его:
variations.Add(new Schedule());- вы создаете новый объект с пустыми значениями.variations[id]- вы ищите пустой созданный объект по его индексу и задаете некоторые далее значения.
Тут собственно вопрос, а почему бы сразу не сделать класс
Scheduleс нужными значениями?Дублирование кода:
Значение
daysу вас идет от 0 и до 5, также значениеlessonsу вас имеет аналогичную нумерацию. Вы это не руками должны писать, а автоматизировать тем же циклом.form.lessons[i1]- Тут тоже нечего такого у вас нет, лишь значение от 1 до 36 и тоже можно автоматизировать.
Исходя из всего этого, ваш код можно сократить до простого:
int itemIndex = 1;
for (int day = 0; day <= 5; day++)
{
for (int lesson = 0; lesson <= 5; lesson++)
{
Console.WriteLine($"[{day}][{lesson}] {itemIndex}");
itemIndex++;
}
}
Вместо Console.WriteLine вы заносите нужные вам объекты туда, куда надо. Результатом данного кода будет:
[0][0] 1
[0][1] 2
[0][2] 3
[0][3] 4
[0][4] 5
[0][5] 6
[1][0] 7
[1][1] 8
[1][2] 9
[1][3] 10
[1][4] 11
[1][5] 12
[2][0] 13
[2][1] 14
[2][2] 15
[2][3] 16
[2][4] 17
[2][5] 18
[3][0] 19
[3][1] 20
[3][2] 21
[3][3] 22
[3][4] 23
[3][5] 24
[4][0] 25
[4][1] 26
[4][2] 27
[4][3] 28
[4][4] 29
[4][5] 30
[5][0] 31
[5][1] 32
[5][2] 33
[5][3] 34
[5][4] 35
[5][5] 36
Как видим, 36 значений, 5 days и 5 lessons, без кучи циклов.
Если пойти дальше, то days и lessons можно сделать коллекциями (List<T>), тогда нам не нужен будет индекс вовсе и можно будет еще сильнее сократить код.
Автор решения: Dzianis Karpuk
→ Ссылка
Разумеется, можно сократить эти 36 циклов. Вот пример
int globalCount = 3; //form.lessons.Count
int[] slots = new int[36]; //по умолчанию проинициализированы нулями
int finishIndex = slots.Length - 1;
do
{
DoSomethingUseful();//полезная нагрузка здесь
//генерация следующего расписания
slots[0]++;
if (finishIndex == 0 && slots[0] == globalCount)
{
break;
}
int overflowIndex = 0;
while (slots[overflowIndex] == globalCount)
{
slots[overflowIndex] %= globalCount;
overflowIndex++;
slots[overflowIndex]++;
if (overflowIndex == finishIndex && slots[overflowIndex] == globalCount - 1)
{
finishIndex--;
}
}
}
while (true);
Только учтите, что изначальная некрасивость вашего кода (36 циклов) отражает сложность алгоритма (n^36), где n - количество вариантов уроков. При n > 2, если у вас нет суперкомпьютера под рукой, вы не сможете дождаться окончания работы алгоритма. При n > 4, вам не поможет даже современный суперкомпьютер.