ххххх
ххх
ххх
хххх
хххх
хххх
хххх
Перебор сочетаний элементов массива
Пишу программу, которая реализует комбинаторно-морфологический метод принятия решений. У меня есть массив вида:
Ну естественно он задан как [7][5], просто остальные его поля содержат 0 и не учитываются. Строки соответствуют функциональным подсистемам, столбцы - альтернативам(ну или конкретным продуктам, среди которых и надо сделать выбор). Данный метод предусматривает полный перебор всех возможных вариантов сочетаний альтернатив подсистем. Таких вариантов будет 5*3*3*4*4*4*4 = 11520.
Так вот как бы реализовать такую генерацию сочетаний?
Код:
Ну естественно он задан как [7][5], просто остальные его поля содержат 0 и не учитываются. Строки соответствуют функциональным подсистемам, столбцы - альтернативам(ну или конкретным продуктам, среди которых и надо сделать выбор). Данный метод предусматривает полный перебор всех возможных вариантов сочетаний альтернатив подсистем. Таких вариантов будет 5*3*3*4*4*4*4 = 11520.
Так вот как бы реализовать такую генерацию сочетаний?
Рекурсивно.
Код:
#include <iostream>
typedef char Value;
Value values[][5]={
{ 'A', 'B', 'C', 'D', 'E' },
{ '1', '2', '3' },
{ '1', '2', '3' },
{ 'a', 'b', 'c', 'd' },
{ 'a', 'b', 'c', 'd' },
{ 'a', 'b', 'c', 'd' },
{ 'a', 'b', 'c', 'd' },
};
void processPattern (Value *v, int len)
{
const char *sep="";
for (; len; v++, len--) {
std::cout << sep << *v;
sep=", ";
}
std::cout << "\n";
}
void generate (int row, Value *result)
{
int rows=(int) sizeof values/sizeof values[0];
if (row>=rows) {
processPattern (result, rows);
return;
}
for (int col=0; col<(int) sizeof values[0]/sizeof values[0][0] && values[row][col]; col++)
{
result[row]=values[row][col];
generate (row+1, result);
}
}
int main ()
{
Value res[sizeof values/sizeof values[0]];
generate (0, res);
}
typedef char Value;
Value values[][5]={
{ 'A', 'B', 'C', 'D', 'E' },
{ '1', '2', '3' },
{ '1', '2', '3' },
{ 'a', 'b', 'c', 'd' },
{ 'a', 'b', 'c', 'd' },
{ 'a', 'b', 'c', 'd' },
{ 'a', 'b', 'c', 'd' },
};
void processPattern (Value *v, int len)
{
const char *sep="";
for (; len; v++, len--) {
std::cout << sep << *v;
sep=", ";
}
std::cout << "\n";
}
void generate (int row, Value *result)
{
int rows=(int) sizeof values/sizeof values[0];
if (row>=rows) {
processPattern (result, rows);
return;
}
for (int col=0; col<(int) sizeof values[0]/sizeof values[0][0] && values[row][col]; col++)
{
result[row]=values[row][col];
generate (row+1, result);
}
}
int main ()
{
Value res[sizeof values/sizeof values[0]];
generate (0, res);
}
Цитата: NewGP
Таких вариантов будет 5*3*3*4*4*4*4 = 11520.
Вот в этом месте не понял. Если память мне не врёт, то количество всех возможных перестановок элементов списка длиной N равно N! (я не вослицаю, это эн факториал). То есть, вам нужно получить перестановки, коих (5! * 3! * 3! * 4! * 4! * 4! * 4!)!, 5! * 3! * 3! * 4! * 4! * 4! * 4! или 7! - какой вариант верен?
Видимо, автор считает так:
В принципе, если порядок использования подсистем не важен, то уникальных перестановок достаточно иметь столько, сколько посчитал автор - каждая подсистема используется только однажды, а перестановок всего получается M в степени N для массива MxN. У автора нули в строках, поэтому получается меньше, ну а максимальное количество перестановок будет равно 78125, если бы в каждой подсистеме было по 5 альтернатив.
В остальных случаях сложность резко возрастает.
Код:
Массив 2х2:
12
34
13 14
23 24
-----
Массив 3х3
123
456
789
Перестановки от 1:
147 148 149
157 158 159
167 168 169
Перестановки от 2:
247 248 249
257 258 259
267 268 269
Перестановки от 3:
347 348 349
357 358 359
367 368 369
Всего 27 перестановок
12
34
13 14
23 24
-----
Массив 3х3
123
456
789
Перестановки от 1:
147 148 149
157 158 159
167 168 169
Перестановки от 2:
247 248 249
257 258 259
267 268 269
Перестановки от 3:
347 348 349
357 358 359
367 368 369
Всего 27 перестановок
В принципе, если порядок использования подсистем не важен, то уникальных перестановок достаточно иметь столько, сколько посчитал автор - каждая подсистема используется только однажды, а перестановок всего получается M в степени N для массива MxN. У автора нули в строках, поэтому получается меньше, ну а максимальное количество перестановок будет равно 78125, если бы в каждой подсистеме было по 5 альтернатив.
В остальных случаях сложность резко возрастает.
Помоему имеется ввиду что надо выбрать ровно одну из первой строки, ровно одну из второй, т.е. вложенные циклы:
Код:
for i1 := 1 to 5 do
for i2 := 1 to 3 do
for i3 := 1 to 3 do
for i4 := 1 to 4 do
for i5 := 1 to 4 do
for i6 := 1 to 4 do
for i7 := 1 to 4 do
letsgo(i1, i2, i3, i4, i5, i6, i7);
for i2 := 1 to 3 do
for i3 := 1 to 3 do
for i4 := 1 to 4 do
for i5 := 1 to 4 do
for i6 := 1 to 4 do
for i7 := 1 to 4 do
letsgo(i1, i2, i3, i4, i5, i6, i7);
Да, и тогда получается, что факториал не нужен. Можно, кстати, избавиться от вложенных циклов и обойтись итератором, обходящим массив. Что-то типа:
Код:
#SelectRightDecision(string) возвращает элемент строки массива, в строке у нас альтернативы подсистем
#DecisionList - список из последовательности альтернатив подсистем
#Язык Boo, код недописан, переменные недообъявлены, но идею пример иллюстрирует.
for string in DecisionArray
DecisionList.Add(SelectRightDecision(string))
#DecisionList - список из последовательности альтернатив подсистем
#Язык Boo, код недописан, переменные недообъявлены, но идею пример иллюстрирует.
for string in DecisionArray
DecisionList.Add(SelectRightDecision(string))