1

这是我发现的排序词典排列的分步过程：

  1. 取先前打印的排列并找到其中最右边的字符，该字符小于其下一个字符。让我们称这个字符为“第一个字符”。

  2. 现在找到“第一个字符”的天花板。天花板是“第一个字符”右侧的最小字符，大于“第一个字符”。让我们将 ceil 字符称为“第二个字符”。

  3. 交换上述 2 个步骤中找到的两个字符。

  4. 在“第一个字符”的原始索引之后对子字符串进行排序（按非递减顺序）。

资料来源：http ://www.geeksforgeeks.org/lexicographic-permutations-of-string/

我已经为它编写了我的伪代码，并且现在也将开始对其进行编程。我了解算法中发生了什么，但我不确定它为什么会起作用。就像第 2 步一样，为什么天花板字符必须是“'第一个字符'右侧的最小字符，大于'第一个字符'”。我知道如果你不这样做，它就不起作用，但我不明白为什么当你这样做时它会起作用。

如果有人可以向我解释为什么你需要算法中的每一步，那就太好了，它会让我在开始我的代码时更加自在。

编辑：我应该提到我理解为什么你将子字符串重新排列为升序，以找到最小的置换，我不明白的是步骤 1 和 2 关于你为什么交换天花板和第一个字符

4

4 回答 4

3

基本上，我们希望将第一个字符从右侧增加尽可能少的数量，并尽可能地减少排列（我们将了解如何做到这一点），剩下的字符保留在它的右侧。我希望，为什么这是我们想要做的事情是非常合乎逻辑的。如果不是，则考虑数字排列（生成一个数字）可能会有所帮助-您可以继续向数字添加一个，直到您得到该数字的另一个排列，尽管一种更有效的方法是神奇地找到我们需要增加的最左边的数字和增加它的数量，并简单地获得右边数字的最小排列，这正是这个算法所做的。

好吧，我们不能只是将一个字符增加到任何其他字符，它需要是一个已经存在于排列中的字符。如果这个字符存在于左侧，那将无济于事，因为它也需要更改左侧的字符，这可能会使我们最终得到更大的排列。所以我们需要在右边使用一个字符，除此之外，它必须是比这个字符大的最小字符。

所以，从右边开始，对于每个字符 A，向右寻找比 A 大的最小字符（称为 B）。如果找不到，请尝试下一个字符。上面的段落解释了我们想要将 A 增加到 B 的值。一旦我们完成了这个，我们就剩下 2 个 B，现在，为了解决这个问题，我们将 B 减小到 A 的值（这实际上只是交换 A 和 B）。从这里我们把所有东西都固定在 A 的右边。由于我们要进行此修复，因此新的 A 现在可能不在它应该在的位置并不重要）。

我们如何修复剩余的字符？好吧，我们想要它们中最小的排列，也就是那些有序的字符。

这需要处理步骤 2-4。

第 1 步呢？这实际上只是算法的优化。如果我们从右边开始并找到右边存在较大字符的第一个字符，那么我们需要找到小于它右侧字符的第一个字符是否有意义，或者，更具体地说，字符在右边一个位置吗？想一想987654321——我们在这里什么也做不了，因为所有的字符都比他们右边的字符大。

用一个例子来解释：

拿ABDC。

右侧存在较大字符的第一个字符是B。大于的最小B字符是C。

所以下一个可能的排列看起来像：（AC??未知?）

剩下的两个字符是D和B，我们需要找到它的最小排列，即BD。所以我们把它放在一起：ACBD。

就交换B和C- 我们需要B成为C（从第 2 段开始），但字符串中仍然需要有 aB才能成为有效的排列（所以我们不能只替换B为）并且在哪里结束C并不重要B向上，因为，紧接着，我们找到了剩余字符的最小排列。

于 2013-07-19T13:14:10.417 回答
2

关于排列的有用链接- 该算法在此处进行了解释。

我也很难理解逻辑，所以这是我对高级概述的看法。

基本上，您排列的元素序列（字符/数字..）可以分为两部分 -前缀和后缀。后缀是从右到“第一个字符”的所有内容。

该算法通过将“第二个字符”（位于后缀中并且是交换元素中较小的一个）与“第一个字符”（它是前缀中最右边的元素并且较大）交换来“增加”前缀一）。选择“第二个字符”和“第一个字符”以表示前缀的最小可能增加。

通过在前缀中尽可能少地增加（通过交换操作完成），您可以说将序列从增加（第一个排列）转换为减少（最后一个排列），您将获得“所有”这些元素的可能序列。

为什么后缀在交换后被排序？为了使后缀“尽可能小”，这样我们就不必在接下来的几次迭代中增加“当前”前缀（当前前缀是指算法这一步中的前缀）

于 2014-04-06T07:31:18.093 回答
1

该算法的主要思想是如何找到给定排列的下一个排列。根据您编写的链接，可以通过在最后打印的排列中找到小于其正确字符的最右侧字符来完成。

证明：

将 P = P[1]p[2]p[3]..p[n] 表示为最后打印的排列。假设 k 是最右边字符的索引，例如 P[k] > P[k+1]。

根据Next的定义，所以Next(P) = P[1]p[2]p[3]..p[k+1]p[k]p[k+2]p[k+3]。 .p[n]。

让我们假设有 P' 这样的 value(P) < value(P') < value(Next(P))。

将 k' 表示为最小索引，例如 P[k'] != P'[k']。

有 3 个选项：

  • k' < k：在这种情况下，因为 value(P') > value(P) ，我们得到 P'[k'] > P[k']。但是直到 k' 索引，Next(P) 和 P 是相同的，所以 P'[k'] > Next(P)[k'] 并且直到 k' 它们是相同的（因为 k' < k) =>与 value(P') < value(Next(P)) 的事实相反。

  • k' > k: P'[k'] > P[k'] 因为value(P') > value(P)，但是我们知道直到k' P和P'相同，所以有k' ' > k' 使得 P[k''] < P[k'] 与 Next 的定义相反（事实上 k 是 P[k] < P[k+1] 的最右边）。那是因为我们可以在链 P[k']P[k'+1]..P[k''] 中找到两个邻居 X,Y，这样 X < Y。

  • k' = k'：如果 Next(P)[k'] < P'[k] 我们将得到不正确的 value(P') > value(Next(P))。如果 P'[k] = Next(P)[k]，因为 k 是最右边的并且因为 value(P') <= value(Next(P)) 我们得到 P' = Next(P) 不能为真，因为值（下一个（P））> 值（P'）。如果 P'[k] < Next(P[k]) 它不能类似于选项 2。

所以我们得到这样的 P' 是不可能的 => Next(P) 是我们想要的 P 的下一个排列。

示例：P = "DFEBCA" Next(P) = "DFECBA"。

所以 k = 4，因为 4 是最右边的索引，例如 P[i] < P[i+1]。

如果你试图找到其他排列 P' 这样的 value(P) < value(P') < value(Next(P)) 你不会找到。

于 2013-07-19T12:52:22.513 回答
0

要打印一个单词的下一个词典术语，我们需要遵循如下所述的算法：-->

  1. 计算单词的长度并使指针指向单词的最后一个和倒数第二个字符。如果倒数第二个字符小于最后一个字符，则交换这两个字符。这是必需的答案。
  2. 如果第一种情况没有发生，则使您的倒数第二个指针（例如 i）减一并搜索大于与位置处的字符但在右侧的子字符串中最小的字符。如果找到这样的字符，则将位置字符与找到的天花板字符（在右侧找到的字符）交换。
  3. 现在，最后对指针右侧的子字符串进行排序，否则重复第二步。
于 2015-02-07T11:49:45.283 回答