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 の場合、ネストされた for ループが 10 個必要になります。

私はこれについて考え、再帰を使用して問題を解決できることに気付きました (各ノードには 0 から 10 までの 10 個の子があり、深さ n で停止するツリーの深さ優先検索)。しかし、私は高パフォーマンスを目指しているので、オーバーヘッドのために再帰を使用したくありません。他にどのような選択肢がありますか?

4

3 に答える 3

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 に答える
3

特定の長さのすべての桁の順列が必要な場合;3桁の例を示したように。3 つのネストされたループを実行する代わりに、10^3 の単一のループを実行すると、すべての順列が得られます。

インデックス作成に使用する場合は、取得した数値を各反復で数字に分割します。

したがって、ネストされたループではなく、1 つのループだけが必要になります。

于 2013-09-11T05:26:11.783 に答える