Иногда возникает в программировании задача, когда надо реализовать переменное количество вложенных циклов, число которых неизвестно, неизвестно также количество повторений каждого цикла. Как быть? В статье предлагается способ с использованием одного лишь цикла, который имитирует множество вложенных циклов.
Содержание
Идея
Количество итераций во множестве вложенных циклов равно произведению прогонов каждого вложенного цикла. Поэтому можно заменить все одним циклом с числом повторений равным этому произведению. Но в циклах важную роль играют индексы, которые меняются от итерации к итерации. Поэтому для имитации вложенности всех циклов надо для каждой итерации нашего одного цикла ставить в соответствие вектор индексов вложенных циклов. Вот этим и займемся.
У меня эта задача возникла при тестировании алгоритмов оптимизации, где множество параметров и их количество у алгоритмов может отличаться, а переписывать каждый раз код из-за разных внешних вложенных циклов не хотелось.
Подготовительные функции
Для реализации идеи вам потребуется две функции, которые приведены ниже:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
template <class T> T HML_ProductOfElementsOfVector(T *VHML_Vector,int VHML_N) { /* Функция вычисляет произведение элементов вектора. Входные параметры: VHML_Vector - указатель на исходный массив; VHML_N - размер массива. Возвращаемое значение: Произведение элементов массива. */ T VHML_Result=1; for (int i=0;i<VHML_N;i++) VHML_Result*=VHML_Vector[i]; return VHML_Result; } //--------------------------------------------------------------------------- void HML_MixedMultiLogicVectorOfFullSearch(int *VHML_Vector, int I, int *HowMuchInElements, int VHML_N) { /* Функция генерирует определенный вектор k-значной логики, где каждый элемент может принимать разное максимальное значение, в полном переборе вариантов. Генерируется I вектор в этом полном переборе. Входные параметры: VHML_Vector - выходной вектор, в который записывается результат; I - номер в массиве в полном переборе, начиная с нуля (от 0 и до произведения всех элементов массива HowMuchInElements - 1); HowMuchInElements - сколько значений может принимать элемент в векторе. То есть элемент может быть 0 и HowMuchInElements[i] - 1; VHML_N - количество элементов в массиве. Возвращаемое значение: Отсутствует. */ int *CountInBlock = new int[VHML_N]; int CountOfAllVariants = HML_ProductOfElementsOfVector(HowMuchInElements, VHML_N); CountInBlock[0] = CountOfAllVariants/HowMuchInElements[0]; for (int i=1;i<VHML_N;i++) CountInBlock[i] = CountInBlock[i-1]/HowMuchInElements[i]; for (int i=0;i<VHML_N;i++) VHML_Vector[i] = (I/CountInBlock[i])%HowMuchInElements[i]; delete [] CountInBlock; } |
Сама реализация
Всё использование показано в примере:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
int N=4;//сколько параметров будет у алгоритма int *R=new int[N];//вектор числа повторений у циклов R[0]=3;//Число повторений у 1 цикла R[1]=3;//Число повторений у 2 цикла R[2]=3;//Число повторений у 3 цикла R[3]=2;//Число повторений у 4 цикла int M=HML_ProductOfElementsOfVector(R,N);//сколько итераций вообще будет int *P=new int[N];//вектор текущих значений индексов имитируемых вложенных циклов //основной цикл for (int i=0;i<M;i++) { HML_MixedMultiLogicVectorOfFullSearch(P, i, R, N);//теперь в P лежат нужные индексы //используем результат } delete[] R; delete[] P; |
Если мы это запустим, то вектор P будет принимать значения:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
P = 0 0 0 0 P = 0 0 0 1 P = 0 0 1 0 P = 0 0 1 1 P = 0 0 2 0 P = 0 0 2 1 P = 0 1 0 0 P = 0 1 0 1 P = 0 1 1 0 P = 0 1 1 1 P = 0 1 2 0 P = 0 1 2 1 P = 0 2 0 0 P = 0 2 0 1 P = 0 2 1 0 P = 0 2 1 1 P = 0 2 2 0 P = 0 2 2 1 P = 1 0 0 0 P = 1 0 0 1 P = 1 0 1 0 P = 1 0 1 1 P = 1 0 2 0 P = 1 0 2 1 P = 1 1 0 0 P = 1 1 0 1 P = 1 1 1 0 P = 1 1 1 1 P = 1 1 2 0 P = 1 1 2 1 P = 1 2 0 0 P = 1 2 0 1 P = 1 2 1 0 P = 1 2 1 1 P = 1 2 2 0 P = 1 2 2 1 P = 2 0 0 0 P = 2 0 0 1 P = 2 0 1 0 P = 2 0 1 1 P = 2 0 2 0 P = 2 0 2 1 P = 2 1 0 0 P = 2 1 0 1 P = 2 1 1 0 P = 2 1 1 1 P = 2 1 2 0 P = 2 1 2 1 P = 2 2 0 0 P = 2 2 0 1 P = 2 2 1 0 P = 2 2 1 1 P = 2 2 2 0 P = 2 2 2 1 |
То есть значения будут именно такими, какими были бы индексы во вложенных циклах. И все идет в том же порядке.