生成 N 嵌套 for 循环的所有值

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 从 -k 到 k 的循环中：

将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

From my research, I understand this should be a recursive solution

完全没有。
请注意，如果您不在不必要的情况下使用递归，则可以避免某些潜在的问题（递归级别和每级别的堆栈增长）并且通常更容易理解代码。

让我们看看你在做什么。如果我们暂时忽略负数，您基本上会生成以下序列（对于 k=2，n=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

如果 k 是 9，您只需用十进制计数即可。在我见过的所有 children 学习计数的人中，我从来不知道有任何人使用递归来学习计数。 ;) 如果你退一步想想你是如何学会计算大数的，你应该找到一个更简单的解决方案....但我会留到以后再说。

如果你用二进制计数，它看起来如下：

或用 k=1 和 n=3 计数（使用 -k 到 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

因此，如果您喜欢冒险，可以：

轻松计算要输出的排列数
使用简单的循环遍历范围
将每个数字转换为基数 k*2+1
通过减去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 是一个非常简单的函数，只要它需要执行 "carry-over".
它通过加 1 来更新当前元素。
但是如果当前元素最大k，它应该回滚到-k，并且"carry-over" +1到左边的数字。
当向量最终达到 {k, k, k, ..., k} 时，每个数字加 1 回滚到 -k 和 VectorInc returns false表示有溢出。

优点：简单，无递归，几乎可以使用任何 k 和 n 值。
缺点：将适用于几乎任何 k 和 n 值。 尝试像 Counter(10, 80) 这样看似无害的调用，您将花费很长时间等待您的程序计算宇宙中的原子数。

生成 N 嵌套 for 循环的所有值

Generating all the values of N nested for loops

c++

recursion

cartesian-product

nested-loops