Генерирующие все значения N вложенных для петель

Question

Я хотел бы написать функцию, чтобы сделать следующее, учитывая два аргумента функции int K и int nest_level генерировать все возможные точки, которые являются результатом создания nest_level вложенных циклов, где каждый цикл колеблется от -K до K. Например, если k = 5 и nest_level = 3 функция печатает последовательности чисел, которые вытекают из следующего:

for(int i = -k; i <= k; ++i) 
    for(int j = -k; j <= k; ++j) 
     for(int m = -k; m <= k; ++m) 
      print(i, j, k) 

Это должно работать для любого K и nest_level

Из моих исследований, я понимаю, что это должно быть рекурсивным решение но я испытываю трудности с его внедрением в C++.

Answer 1

Использовать std::vector. Передайте его по ссылке. В цикле от I -к до к:

• толчок i в него.

• Если длина вектора равна уровню гнезда, напечатайте.

• В противном случае, рекурсия, прохождение в векторе по ссылке.

• Теперь выскочите последний элемент с конца вектора и продолжите цикл.

Answer 2

Что-то вроде этого, вам нужен контейнер для хранения номер

#include "iostream" 
#include "vector" 

void print(const std::vector<int>& v) { 
    for (auto i : v) { 
     std::cout << i << ' '; 
    } 
    std::cout << std::endl; 
} 

void genImpl(int K, int level, std::vector<int>& cache) { 
    if (level == 1) { 
     for (int i = -K; i <= K; ++i) { 
      cache.push_back(i); 
      print(cache); 
      cache.pop_back(); 
     } 
    } else { 
     for (int i = -K; i <= K; ++i) { 
      cache.push_back(i); 
      genImpl(K, level - 1, cache); 
      cache.pop_back(); 
     } 
    } 
} 

void gen(int K, int level) { 
    std::vector<int> cache; 
    genImpl(K, level, cache); 
} 

int main() { 
    gen(2, 3); 
    return 0; 
} 

Answer 3

because both parameters are int type, so ,first you should get their abs value. 

//pseud0-code 

{ 
    k = abs(k); 
    nest_level = abs(nest_level); 
    while(nest_level--){ 
    for(int i = -k; i < k; i++){ 
     printf("%d,%d", nest_level, i); 
    } 
    printf("\r\n"); 
    } 
} 

Answer 4

Другой способ думать об этой проблеме, что вы работаете с номером, где каждая цифра колеблется от -K до K. Вы можете увеличивать (-K) (- K) (- K) ... (- K) (- K) (- K) до KKK ... KKK и печатать промежуточные результаты.

#include <iostream> 
#include <vector> 

bool increment(int K, std::vector<int> & vals) { 
    int position = vals.size()-1; 
    while (vals[position] == K) { 
     vals[position] = -K; 
     --position; 
     if (position == -1) { 
      return false; 
     } 
    } 
    ++vals[position]; 
    return true; 
} 

void count(int K, int nest_level) { 
    std::vector<int> vals; 
    for (int n=0; n<nest_level; ++n) { 
     vals.push_back(-K); 
    } 

    do { 
     for (auto v : vals) { 
      std::cout << v << " "; 
     } 
     std::cout << "\n"; 
    } while (increment(K, vals)); 
} 

int main() 
{ 
    count(1, 2); 
    return 0; 
} 

Я не уверен, какой путь лучше, но я решил, что это была аккуратная параллель.

Answer 5

Из моих исследований, я понимаю, что это должно быть рекурсивным решением

Вовсе нет.
Обратите внимание, что если вы не используете рекурсию без необходимости, вы можете избежать определенных потенциальных проблем (уровни рекурсии и рост стека на уровень), и часто легче понять код.

Давайте посмотрим, что вы делаете. Если мы будем игнорировать отрицательные числа на данный момент, вы в основном генерируя следующую последовательность (при к = 2, п = 4):

0 0 0 0  0 1 0 0  0 2 0 0 
0 0 0 1  0 1 0 1  0 2 0 1 
0 0 0 2  0 1 0 2  0 2 0 2 
0 0 1 0  0 1 1 0  0 2 1 0 
0 0 1 1  0 1 1 1  0 2 1 1 
0 0 1 2  0 1 1 2  0 2 1 2 
0 0 2 0  0 1 2 0  0 2 2 0 
0 0 2 1  0 1 2 1  0 2 2 1 
0 0 2 2  0 1 2 2  0 2 2 2 

Если к 9 были просто бы подсчет в десятичной системе счисления. Из всех детей, которых я видел, научиться считать, я никогда не знал, чтобы это делалось с помощью рекурсии. ;) Если вы отступите и подумайте о том, как вы научились считать большие числа, вы должны найти гораздо более простое решение ... Но я сохраню это позже.

Если считать в двоичной системе это будет выглядеть следующим образом:

0 = 000 
1 = 001 
2 = 010 
3 = 011 
4 = 100 
5 = 101 
6 = 110 
7 = 111 

Или подсчитывать с k=1 и n=3 (используя -k к):

0 = -1 -1 -1  9 = 0 -1 -1  18 = 1 -1 -1 
1 = -1 -1 0  10 = 0 -1 0  19 = 1 -1 0 
2 = -1 -1 1  11 = 0 -1 1  20 = 1 -1 1 
3 = -1 0 -1  12 = 0 0 -1  21 = 1 0 -1 
4 = -1 0 0  13 = 0 0 0  22 = 1 0 0 
5 = -1 0 1  14 = 0 0 1  23 = 1 0 1 
6 = -1 1 -1  15 = 0 1 -1  24 = 1 1 -1 
7 = -1 1 0  16 = 0 1 0  25 = 1 1 0 
8 = -1 1 1  17 = 0 1 1  26 = 1 1 1 

Так что, если вы чувствуете вы можете:

• легко вычислить количество перестановок t о выходной
• использовать простой цикл для цикла через диапазон
• преобразовать каждое число в базовые к * 2 +-
• смещения каждой цифра вычитания K

Конечно, есть и более простой подход намекала раньше. Вызовите Counter(k, nest_level); в коде ниже. (Объяснение после)

void WriteVector(const std::vector<int>& v) 
{ 
    for (const auto i : v) 
     std::cout << i << " "; 
    std::cout << std::endl; 
} 

bool VectorInc(const int k, std::vector<int>& v) 
{ 
    for (auto it = v.rbegin(); it != v.rend(); it++) 
    { 
     if ((*it) < k) { 
      (*it)++; 
      return true; 
     } 
     (*it) = -k; 
    } 
    return false; 
} 

void Counter(const int k, const int n) 
{ 
    std::vector<int> v(n, -k); 
    WriteVector(v); 
    while (VectorInc(k, v)) 
     WriteVector(v); 
} 

• Counter инициализирует вектор с size == nest_level и каждый элемент, содержащий -k.
• В цикле он вызывает VectorInc, чтобы имитировать добавление 1 (или подсчет).
• VectorInc - очень простая функция, которая проходит через векторные элементы справа налево до тех пор, пока ей необходимо выполнить «перенос».
• Он обновляет текущий элемент путем добавления 1.
• Но если текущий элемент это при максимальной k, он должен пролонгировать обратно -k, и «переброс» +1 к цифре слева.
• Когда вектор в конечном итоге достигает {k, k, k, ..., k}, добавляя 1 рулоны каждой цифру обратно -k и VectorInc возвращает ложные указывающих произошло переполнение.

Pros: Простой, без рекурсии, и будет работать с почти любыми значениями K & п.
Против: Будет работать практически с любыми значениями k & n. Попробуйте, казалось бы, безобидный вызов, например Counter(10, 80), и вы будете долго ждать, пока ваша программа будет считать атомы во вселенной.