在输入中我有一个“n”数字，它是排列的大小，我必须打印包含 n 个数字(从 1 到 n)的所有可能的排列，但我必须拒绝那些有“231方案”的
“231方案”的意思是在排列中我们可以找到这样三个连续的数字(x，y，z)将适用于不等式z(1<2<3)。
因此，例如对于 n=4，我们有 4! = 24 个排列。我们拒绝了其中的九个......
- 4231、2431、2341、2314 - 因为他们有 231
- 2413, 3241 - 因为他们有 241
- 3412、3421 - 因为他们有 341(和 342)
- 1342 - 因为它有 342
...并打印其他十五种可能性。
好的，这就是问题所在。我已经花了很多时间思考这个任务。我想出了这样的事情:
我们可以为 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”，我们从最终答案中拒绝它。
如果有任何意见、想法和提示，我将不胜感激。我意识到我的想法可能毫无用处，但那是我最好的。那么还有其他(可能更智能和/或更复杂的)方法吗？
最佳答案
你的想法是正确的。通过将 1 添加到 n 来迭代构建您的排列。当您添加 i 时，您只需检查 i 是否不存在您希望避免的模式。
例如，如果模式是 231，则检查 i 左侧的任何内容是否大于 i 右侧的任何内容>。
如果您想打印所有结果而不是生成它们(这避免了存储问题)，那么您可以按字典顺序进行排列。扫描前缀，如果在任何时候存在模式，例如在第一个 k 字母中，然后移动到下一个前缀。这将加快迭代速度。
关于algorithm - 避免排列模式 - 在没有 231 方案的情况下打印所有排列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10471705/