在输入端我有一个“n”数，这是排列的大小，我必须打印包含n个数的所有可能的排列（从1到n），但我必须拒绝使用“231方案”的排列。
“231方案”是指在置换中我们可以找到这三个连续数（x，y，z），它们将应用于不等式z（1例如，n=4，我们有4！=24个置换。我们拒绝了其中的九个…
4231243123412314-因为他们有231
因为他们有241
34123421-因为他们有341（和342）
1342-因为它有342个
…然后打印其他15个可能性。
好吧，这就是问题所在我已经花了很多时间考虑这个任务了我发现了这样的事情：
我们可以为n=3生成置换，拒绝231，然后（对于n=4）基于先前生成的置换生成所有可能性。
所以我选择132个排列。现在我们在所有可能的方式上“插入”4：
4132，
1432年，
1342年，
一千三百二十四
我们可以肯定地说，第一个和最后一个排列是好的，所以我们必须更接近其他两个。我的想法是从“4”左边的数字中找出最高的数字，从“4”右边的数字中找出最低的数字。
如果左最大值>右最小值，我们就有了“231方案”。
例如，置换1342:left_max=3，right_min=2，所以它是正确的“231”，我们从最终答案中拒绝它。
我会非常感谢任何评论，想法和提示我知道我的想法可能没用，但那是我最好的那么还有其他方法（可能更聪明和/或更好的复杂性）吗？
最佳答案
你的想法是对的。通过将1添加到n来迭代地构建排列。添加i时，只需检查希望避免的模式是否与i一起出现。
例如，如果模式是231，则检查i左侧的内容是否大于i右侧的内容。
如果你想打印所有结果而不是生成它们（这避免了存储问题），那么你可以通过字典来进行排列。扫描前缀，如果在任何点上存在模式，例如在第一个k字母中，则转到下一个前缀。这将加快迭代的速度。