c ++:嵌套for循环的动态数量(无递归)

Question

我正在编写一个代码段,遍历n个数字的每个排列.因此,例如,如果n = 3,我想迭代以下每个元素:

0,0,0

...

0,1,0

...

1,0,0

...

2,3,4

...

9,9,9

使用嵌套for循环很容易编码:

for(digit1 0 to 9)
    for(digit2 0 to 9)
        for(digit3 0 to 9)

但我想将这个概括为n位数.如果例如n = 10,我现在需要10个嵌套for循环.

我已经考虑过这个并且意识到问题可以通过递归来解决(深度优先搜索树,每个节点有10个子节点,0到10,并且在深度n处停止).但我的目标是高性能,所以我不想因为开销而使用递归.我还有其他什么选择？

Answer 1

如果要在不使用递归的情况下使用单个模拟嵌套循环,可以通过为每个循环变量维护一组状态(或插槽)来实现,这可以通过数组轻松完成.循环然后变成一个简单的问题"向该数组添加1",根据需要执行进位操作.如果你的嵌套深度是n,并且你的每个循环的最大边界是b,那么它的运行时间是O(b ^ n),因为进位操作最多只花费你O(b ^ n)(我会在这里跳过代数).

这是工作的C++代码(更新以集成Drew的注释):

void IterativeNestedLoop(int depth, int max)
{
    // Initialize the slots to hold the current iteration value for each depth
    int* slots = (int*)alloca(sizeof(int) * depth);
    for (int i = 0; i < depth; i++)
    {
        slots[i] = 0;
    }

    int index = 0;
    while (true)
    {
        // TODO: Your inner loop code goes here. You can inspect the values in slots

        // Increment
        slots[0]++;

        // Carry
        while (slots[index] == max)
        {
            // Overflow, we're done
            if (index == depth - 1)
            {
                return;
            }

            slots[index++] = 0;
            slots[index]++;
        }

        index = 0;
    }
}

Answer 2

在一般情况下，如果您想将递归替换为平面代码，您应该使用堆栈（LIFO）。所以如果你有递归算法：

void print(std::string str, int depth)
{
  if (depth == n) {
    std::cout << str << std::endl;
    return;
  }

  for (int i = 0; i < 10; ++i) {
    char val[2] = { i + '0', 0 };
    print(str + val + ", ", depth+1);
  }
}

您可以将其转换为基于 LIFO 并保存局部变量（本例中为 str 和 i）：

struct StackItem {
  StackItem(const std::string& ss, unsigned ii)
    : str(ss), i(ii)
    {}
  std::string str;
  int i;
};

void print_norec()
{
  std::list< StackItem > stack;
  stack.push_back(StackItem("", 0));
  while (!stack.empty()) {
    StackItem& current = stack.back();
    if (stack.size() == n+1) {
      std::cout << current.str << std::endl;
      stack.pop_back(); // return from "recursive" function
      continue;
    }
    if (current.i < 10) {
      char val[2] = { current.i + '0', 0 };
      // call "recursive" function
      stack.push_back(StackItem(current.str + val + ", ", 0)); 
      current.i++;
    } else {          
      stack.pop_back(); // return from "recursive" function
    }
  }
}

Answer 3

如果您想要特定长度的所有数字的排列；如您所示的 3 位数字的示例。不要运行 3 个嵌套循环，而是运行一个 10^3 的循环，这将为您提供所有排列。

如果您想将每次迭代中获得的数字用于索引，请将其拆分为数字。

因此，您将只需要一个循环而不是嵌套循环。