字典（字典）顺序排列[关闭]

Question

给定 a,b,c,d,e,f,g,h,i,j 的以下排列，previous 字典序（字典）顺序的排列是什么？写下你的答案，字母之间不要有空格。

ghadbicefj

我尝试将“ghadbicefj”的字典顺序排列为“ghadbicefj”→“ghadbice fj”。

我想确认我的答案

Answer 1

你好像没有做排列，而是插入了一个空格。排列是您更改给定字符顺序的位置。

“abcdefghij”在词汇顺序中的排列是这样开始的：

 abcdefghij
 abcdefghji
 abcdefgijh
 abcdefgihj
 ...

在某个时候它会到达“ghadbicefj”，问题是确定哪个排列出现在它之前。该“社区”中的顺序是这样的：

...
ghadbfjeic
ghadbfjice
ghadbfjiec
ghadbicefj
ghadbicejf
ghadbicfej
ghadbicfje 
...

答案是“ghadbfjiec”。

确定它的算法如下：

1. 从右边开始，找到第一个大于其后继的字符。如果没有，则没有前一个：然后输入给出词法顺序中的第一个排列。对于示例字符串，这个字符是“i”，因为它大于“c”，而“c”、“e”和“f”都小于它们的后继字符。

2. 考虑找到的位置右侧的部分。在示例中，该部分是“cefj”。我们知道该部分中的字符按非递减顺序排序（因为上一步）。从该部分中，选择小于步骤 1 中找到的字符的字符中最大的字符。在“f”的示例中。

3. 交换找到的两个字符。在这个例子中，这意味着我们交换“i”和“f”。这意味着第2步的部分仍然按非递减顺序排序。在这个例子中，那个部分变成了“ceij”。然后反转该部分。在该部分变为“jiec”的示例中。

当你用 Python 标记它时，这里是实现上述算法的代码：

def previous_permutation(s):
    for i in range(len(s) - 2, -1, -1):
        if s[i] > s[i + 1]:
            for k in range(len(s) - 1, i, -1):
                if s[i] > s[k]:
                    return s[:i] + s[k] + s[-1:k:-1] + s[i] + s[k-1:i:-1]

s = "ghadbicefj"
p = previous_permutation(s)
print(p)  # ghadbfjiec

Answer 2

你的答案不正确。 “ghadbicefj”的字典顺序的前一个排列是“ghadbicjef”。

要理解原因，您可以从比较给定排列的最后两个字母“f”和“j”开始。由于“f”在字母表中出现在“j”之前，您不能简单地交换它们以获得之前的排列。

接下来，您需要找到最右边的一对字母，其中左边的字母小于右边的字母。在这种情况下，它是“c”和“j”。您需要交换它们，然后将剩余的字母以相反的顺序排序到“c”的右侧，以获得之前的排列。

所以，“ghadbicefj”→“ghadbicjef”。

请注意，您不需要在答案中的字母之间添加任何空格。