17

我正在编写一个代码段，它遍历 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 处停止）。但我的目标是高性能，所以我不想因为开销而使用递归。我还有什么其他选择？

4

3 回答 3

15

如果您想在不使用递归的情况下使用单个循环来模拟嵌套循环，您可以通过为每个循环变量维护一组状态（或插槽）来实现，这可以通过数组轻松完成。然后循环变成一个简单的问题，即向该数组“加 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;
    }
}
于 2015-06-12T16:51:06.607 回答
3

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

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

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

于 2013-09-11T05:26:11.783 回答
3

在一般情况下，如果您想将递归替换为平面代码，您应该使用堆栈（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);
  }
}

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

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
    }
  }
}
于 2013-09-11T05:49:22.427 回答