下一个词法“排列”算法

Question

我编写了一个程序，解决了24的通用版本（为好奇的人提供链接）。也就是说，给定一组n数，有没有办法对它们执行二进制运算，以便它们计算到目标数。

为此，我将可能的表达式视为由'v'或'o'组成的char数组，其中'v'是值的占位符，'o'是操作的占位符。请注意，如果有n值，则必须有n-1操作。

程序当前的工作方式是按字典顺序检查{'o'，'o'，…，'v'， v'…}的每个排列，并查看前缀表达式是否有效。例如，当n=4时，以下表达式被认为是有效的：

{'o'，'o'，'v'，'v'，'v'，'v'}
{'o'，'v'，'o'，'v'，'o'，'v'，'v'}

以下表达式无效：

{'v'，'o'，'v'，'o'，'o'，'v'，'v'}

{'o'、'o'，'v'、'v'，'v'、'o'、'v'}

我的问题是，是否存在一种有效的算法来得到在某种排序中有效的下一个排列？目标是消除检查表达式是否对每个排列都有效的必要。

此外，如果存在这样的算法，是否存在计算第k个有效置换的O（1）时间？

我假设长度为< code>2n-1的前缀表达式< code>A当且仅当

操作数

其中＜code＞0

此外，这意味着确实存在（1/n）C（2n-2，n-1）有效置换，其中C（n，k）是 。




Answer 1

下面是如何生成ov-模式。下面代码背后的细节在Knuth第4A卷中（或者至少提到了；我可能做过其中一个练习）。在更改模式之前，可以使用现有的排列机制以各种方式排列值。

密码

#include <cstdio>

namespace {
void FirstTree(int f[], int n) {
  for (int i = n; i >= 0; i--) f[i] = 2 * i + 1;
}

bool NextTree(int f[], int n) {
  int i = 0;
  while (f[i] + 1 == f[i + 1]) i++;
  f[i]++;
  FirstTree(f, i - 1);
  return i + 1 < n;
}

void PrintTree(int f[], int n) {
  int i = 0;
  for (int j = 0; j < 2 * n; j++) {
    if (j == f[i]) {
      std::putchar('v');
      i++;
    } else {
      std::putchar('o');
    }
  }
  std::putchar('v');
  std::putchar('\n');
}
}

int main() {
  constexpr int kN = 4;
  int f[1 + kN];
  FirstTree(f, kN);
  do {
    PrintTree(f, kN);
  } while (NextTree(f, kN));
}

生成输出

ovovovovv
oovvovovv
ovoovvovv
oovovvovv
ooovvvovv
ovovoovvv
oovvoovvv
ovoovovvv
oovovovvv
ooovvovvv
ovooovvvv
oovoovvvv
ooovovvvv
oooovvvvv

有一种方法可以得到第k棵树，但时间是O（n）而不是O（1）。神奇的单词是解开二叉树的等级。