c++ - 下一个词法 "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’}

我的问题是是否存在一种有效的算法来获得下一个在某种排序中有效的排列？目标是无需检查表达式是否对每个排列都有效。

此外，如果存在这样的算法，是否存在O(1)是时候计算 k 了第一个有效排列？

到目前为止我有什么

我假设前缀表达式 A长度2n-1当且仅当

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 .