问题描述
这是一步一步的过程中，我发现订购辞书排列：
This is the step by step process I found for ordering lexicographical permutations:
-
采取previously印刷置换并找到最右边的字符在它，这是比其下一个字符较小。让我们把这个字符作为第一个字符。
Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.
现在找到的第一个字符的上限。天花板上的第一个字符'，这是大于第一字符的右边的最小字符。让我们致电CEIL字符作为第二个字符。
Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.
交换两个字符发现上述2步。
Swap the two characters found in above 2 steps.
排序子（非递减顺序排列）的第一个字符的原始索引之后。
Sort the substring (in non-decreasing order) after the original index of ‘first character’.
来源： http://www.geeksforgeeks.org/lexicographic-permutations-of -string /
我已经写了我的假$ C $下它，我即将开始现在编程以及。我明白发生了什么，在算法，但我不知道为什么它的工作原理。像上的步骤2为什么必须在天花板字符是上的第一字符'，这是大于第一字符的右边的最小字符。据我所知，这并不重要，如果你不这样做，这样的工作，但我不明白为什么它当你做的工作。
I have already written my Pseudo-code for it,and am about to start programming it now as well. I understand what is happening in the Algorithm, but I am not sure why it works. Like on Step 2 why must the ceiling character be "the smallest character on right of ‘first character’, which is greater than ‘first character'". I understand that it doesn't work if you don't do it this way, but I don't understand why it does work when you do.
如果有人可以给我解释一下为什么你需要在算法中的每一步，这将是伟大的，它会让我更舒服，开始我的code。
If someone could explain to me why you need to each step in the algorithm that would be great and it would make me far more comfortable in starting my code.
编辑：我应该提到我明白你为什么rearange的子成acsending顺序，找到最小的置换，是什么我不明白的是步骤1和2，为什么你交换的天花板和第一charector
I should mention I understand why you rearange the substring into acsending order, as to find the smallest permute, what I dont understand is the step 1 and 2 as to why you swap the ceiling and the first charector
推荐答案
基本上，我们希望通过尽可能小的量，以增加从右侧的第一个字符，我们可以做出尽可能小的置换（我们会得到我们怎么办此）与剩余它的右侧的字符。为什么这是我们想要做的是什么，我希望，pretty的逻辑。如果不是，它可以帮助想在数字（使得一些）置换方面 - 你可以继续加1的号码，直到你到达这个数字的另一种排列，虽然方式更有效的方法是奇迹般地找到最左边的数字，我们需要增加的量增加，并简单地得到的数字最小的置换来的权利，这正是这个算法一样。
Basically we want to increase the first character we can from the right by the smallest possible amount and make the smallest possible permutation (we'll get to how we do this) with the characters remaining to the right of it. Why this is what we want to do is, I hope, pretty logical. If it isn't, it may help to think in terms of a permutation of digits (making a number) - you could keep adding one to the number until you get to another permutation of that number, though a way more efficient method would be to magically find the left-most number we need to increase and the amount to increase it by and simply get the smallest permutation of the digits to the right, which is exactly what this algorithm does.
那么可以不只是一个字符增加任何其它的字符，它需要一个已经存在于排列的字符。而如果这个角色存在的左边，不会真正的帮助，因为这将需要改变字符的左侧为好，这将让我们有可能结束了一个更大的置换。因此，我们需要用一个字符的权利，在此之上，它必须是最小的字符大于这个人物。
Well, we can't just increase a character to any other character, it needs to be a character that already exists in the permutation. And if this character exists to the left, that won't really help, as it will require changing the character that's to the left as well, which will have us potentially end up with a much larger permutation. So we need to use a character to the right and, on top of this, it must be the smallest character that is bigger than this character.
所以，走在正确的，并为每个字符A，适合的最小字符大于A（称之为B）的样子。如果你没有找到一个，尝试下一个字符。上面这段解释说，我们要增加A到B的值。一旦我们做到了这一点，我们只剩下2 B的，现在，要解决这个问题，我们降低B到A的值（这基本上只是交换A和B）。从这里我们解决一切的，其中A是正确的。既然我们要做到这一点固定，它并不真正的问题是，新的A现在可能不是它应该是）。
So, go from the right and, for each character A, look right for the smallest character larger than A (call this B). If you don't find one, try the next character. The above paragraph explains that we want to increase A to B's value. Once we've done this, we are left with 2 B's, now, to fix this, we decrease B to A's value (this is essentially just swapping A and B). From here we fix everything to the right of where A was. Since we're going to do this fixing, it doesn't really matter that the new A now might not be where it should be).
我们如何解决剩余的字符？好了，我们希望他们的最小的排列，这简直是这些字符排序。
How do we fix the remaining characters? Well, we want the smallest permutation of them, which is simply those characters ordered.
这是需要照顾的步骤2-4。
That takes care of steps 2-4.
那么第1步？这实际上是该算法的只是一个优化。如果我们从右边去和寻找，从而存在较大的字符右侧的第一个字符，将不是让我们需要找到的第一个字符，它比一个字符到它的右侧较小的意义，或者更具体地说，字符的一个位置到它的正确？想想 987654321 - 我们不能做任何事情，在这里，因为所有的字符不是直接的人物在其右侧大
What about step 1? This is actually just an optimization of the algorithm. If we're going from the right and finding the first character for which there exists a larger character to the right, won't it make sense that we need to find the first character that's smaller than a character to the right of it, or, more specifically, the character one position to the right of it? Think about 987654321 - we can't do anything here since all the characters are larger than the characters directly to their right.
要举个例子来说：
取 ABDC 。
，从而存在较大的字符到右边的第一个字符是 B 。在最小的角色比 B大是 C 。
The first character for which there exists a larger character to the right is B. The smallest character larger than B is C.
因此，接下来可能的排列将是这样的： AC ?? （ 是未知的？）
So the next possible permutation will look like: AC?? (? is unknown)
剩下的两个字符是 D 和 B ，这是我们需要找到的最小的排列，这是 BD 。因此，我们把它一起： ACBD
The two remaining characters are D and B, which we need to find the smallest permutation of, which is BD. So we put it together: ACBD.
在条件交换 B 和 C - 我们需要 B 成为 C （从第2款），但仍然需要一个 B 的字符串它是一个有效的置换（所以我们不能只替换 B 与 C ），这不要紧， B 结束了，因为，正确的事后，我们找到了剩余的字符的最小置换。
In terms swapping B and C - we need B to become C (from paragraph 2), but there still needs to be a B in the string for it to be a valid permutation (so we can't just replace B with C) and it doesn't matter where B ends up, since, right afterwards, we find the smallest permutation of the remaining characters.
这篇关于请问这个算法生成下字典序排列有序的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！