2

在输入中，我有一个“n”数，它是排列的大小，我必须打印包含 n 个数字（从 1 到 n）的所有可能排列，但我必须拒绝带有“231 方案”的排列

“231 方案”意味着在排列中我们可以找到适用于不等式 z (1<2<3) 的三个连续数 (x, y, z)。

因此，例如对于 n=4，我们有 4！= 24 个排列。我们拒绝其中九个...

  • 4231, 2431, 2341, 2314 - 因为他们有 231
  • 2413, 3241 - 因为他们有 241
  • 3412、3421 - 因为他们有 341（和 342）
  • 1342 - 因为它有 342

...并打印其他 15 个可能性。

好的，这就是问题所在。我已经花了很多时间思考这个任务。我想出了这样的事情：

我们可以为 n=3 生成排列，拒绝 231，然后（对于 n=4）基于先前生成的可能性生成所有可能性。

所以我会选择一个 132 排列。现在我们以所有可能的方式“插入”4：4132、1432、1342、1324。我们可以肯定地说，第一个和最后一个排列都很好，所以我们必须更接近其他两个排列。我的想法是从“4”左侧的数字中找到最大的数字，从“4”右侧的数字中找到最小的数字。如果 left_max>right_min，我们就有了“231 方案”。

例如排列 1342：left_max=3，right_min=2，所以它是正确的“231”，我们从最终答案中拒绝它。

我会非常感谢任何评论、想法和提示。我意识到我的想法可能毫无用处，但这是我最好的。那么还有其他（可能更聪明和/或更复杂）的方法吗？

4

2 回答 2

1

你有正确的想法。1通过加起来迭代地构建你的排列n。添加时i，您只需检查您希望避免的模式是否不存在i。

例如，如果模式是231，则检查左侧的i任何内容是否大于右侧的任何内容i。

如果您想打印所有结果而不是生成它们（这避免了存储问题），那么您可以按字典顺序进行排列。扫描前缀，如果模式在任何点出现，例如在第一个k字母中，则继续下一个前缀。这将加快迭代速度。

于 2012-05-06T20:32:42.637 回答
0

这可能是一顶旧帽子，但只是补充一点：避免 231 的排列数是加泰罗尼亚数，可以估计为 O(2^(2n)) （它们也有一个很好的封闭公式）。准确地说，对于 n=15，我们将有 9,694,845 个数字。

使用加泰罗尼亚数的递归公式 在此处输入图像描述

我们也可以为避免 231 的排列构建递归：

all_perms(n):
    if (n=0) return [1];
    out = [];
    for i=1,...,n:
        for perm1, perm2 in all_perms(i-1), all_perms(n-i):
            increase all elements in perm2 by i-1;
            append n to perm1 (from the right), then append perm2 to that (from the right);
        add the result of appending into out;

您可以使用动态编程/记忆化进一步细化此算法。

于 2019-06-07T04:32:49.373 回答