下一个词法 "permutation" 算法

Question

我写了一个程序来解决 24 的通用版本（link 对于那些好奇的人）。也就是说，给定一组 n 个数字，是否有一种方法可以对它们执行二进制运算，以便它们计算出目标数字。

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

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

{‘o’,’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) 时间？

到目前为止我有什么

我假设长度为 2n-1 的前缀表达式 A 被认为是有效的当且仅当

number of operations < number of values 每个 A[i:2n-1)

其中 0<=i<2n-1（从 i 开始到 2n-1 结束（不包含）的子数组）

此外，这意味着恰好有 (1/n)C(2n-2,n-1) 个有效排列，其中 C(n,k) 是 n choose 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)。神奇的词是 unranking binary trees.

下一个词法 "permutation" 算法

Next lexical "permutation" algorithm

c++

algorithm

permutation

到目前为止我有什么