这是我找到的用于排序字典排列的分步过程:
采用先前打印的排列并找到其中最右边的字符,该字符小于其下一个字符。让我们称这个字符为“第一个字符”。
现在找到“第一个字符”的上限。 Ceiling是‘first character’右边最小的字符,大于‘first character’。让我们将 ceil 字符称为“第二个字符”。
交换上面两步找到的两个字符。
在'第一个字符'的原始索引之后对子字符串进行排序(以非递减顺序)。
来源:http://www.geeksforgeeks.org/lexicographic-permutations-of-string/
我已经为它编写了我的伪代码,现在也将开始对其进行编程。我了解算法中发生的事情,但我不确定它为什么有效。就像在步骤 2 中一样,为什么上限字符必须是“‘第一个字符’右侧的最小字符,它大于‘第一个字符’”。我知道如果你不这样做是行不通的,但我不明白为什么当你这样做时它会起作用。
如果有人能向我解释为什么您需要了解算法中的每一步,那就太好了,这会让我在开始编写代码时更加自在。
编辑:我应该提一下,我理解为什么要将子字符串重新排列为升序,以找到最小的排列,我不明白的是第 1 步和第 2 步为什么要交换上限和第一个字符
最佳答案
基本上,我们希望从右边开始的第一个字符增加尽可能少的数量,并进行尽可能小的排列(我们将了解如何做到这一点),其中的字符保留在它的右边。我希望,为什么这就是我们想要做的,这是非常合乎逻辑的。如果不是,则考虑数字排列(生成数字)可能会有所帮助 - 您可以继续将数字加一个,直到获得该数字的另一种排列,但更有效的方法是神奇地找到我们需要增加的最左边的数字以及增加它的数量,并简单地获得右边数字的最小排列,这正是该算法所做的。
好吧,我们不能只是将一个字符增加到任何其他字符,它需要是一个已经存在于排列中的字符。如果这个字符存在于左侧,那也无济于事,因为它也需要更改左侧的字符,这将使我们最终可能得到更大的排列。所以我们需要在右边使用一个字符,在此之上,它必须是比这个字符大的最小字符。
因此,从右边开始,对于每个字符 A,向右查找比 A 大的最小字符(称为 B)。如果找不到,请尝试下一个字符。上面的段落解释了我们要增加 A 到 B 的值。一旦我们完成了这个,我们就剩下 2 个 B,现在,为了解决这个问题,我们将 B 减少到 A 的值(这实际上只是交换 A 和 B)。从这里开始,我们将所有内容都固定在 A 所在位置的右侧。由于我们要进行此修复,因此新 A 现在可能不在应有的位置并不重要)。
我们如何修复剩余的字符?好吧,我们想要它们的最小排列,也就是那些有序的字符。
这会处理第 2-4 步。
第一步呢?这实际上只是算法的优化。如果我们从右边开始并找到第一个字符,右边有一个更大的字符,那么我们需要找到第一个比它右边的字符小的字符是否有意义,或者,更具体地说,是字符右边一个位置吗?想想 987654321
- 我们不能在这里做任何事情,因为所有字符都比直接在它们右边的字符大。
举例说明:
以ABDC
为例。
右侧存在较大字符的第一个字符是B
。大于B
的最小 字符是C
。
所以下一个可能的排列如下:AC??
(?
未知)
剩下的两个字符是D
和B
,我们需要找到它们的最小排列,也就是BD
。所以我们把它放在一起:ACBD
。
在交换 B
和 C
方面——我们需要 B
变成 C
(来自第 2 段),但是字符串中仍然需要一个 B
才能成为一个有效的排列(所以我们不能只用 C
替换 B
) 并且 B
在哪里结束并不重要,因为紧接着,我们找到了剩余字符的最小排列。
关于algorithm - 这个用于生成下一个字典顺序排列的算法是如何工作的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17745870/