Go实现字符串全排列字典序排列详解

作者 | 陌无崖

转载请联系授权

字典序

百度百科

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法

维基百科

给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔积 A × B，则字典序定义为(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′).

简单理解

在我们进行查找英文词典的时候，我们如何进行查找，我们会依次的进行从首字母进行查找，那我们逆向思维，如果我们想要这样的查找我们应该怎么去存储我们的英语，不同的英语如何进行排序呢？对于两个英语abc 和 acb显然我们先比较我们的a，发现相同，寻找各自的第二个字符，谁小，我们就把小的放在前面。按照这样的方式我们强制规定了一个顺序。

题目思路

假定现有字符串(A)x(B)，它的下一个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且一定有y > x。那么，为使下一个排列字典顺序尽可能小，必有：

• A尽可能长
• y尽可能小
• B’里的字符按由小到大递增排列 那么如何找x和y呢？

举例

现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），我们可以看到最后一个能增大的数是：x = 1。 而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，于是我们最终找到“21543”大但字典顺序尽量小的23145，找到的23145刚好比21543大。

代码逻辑

定义升序 相邻两个位置ai < ai+1，ai 称作该升序的首位 步骤（二找、一交换、一翻转）

• 找到排列中最后（最右）一个升序的首位位置i，x = a[i]
• 找到排列中第i位右边最后一个比a[i] 大的位置j，y = a[j]
• 交换x，y
• 把第(i+ 1)位到最后的部分翻转

注意 在代码逻辑的第二步骤中我们强调了最后一个，但是在举例中的我们强调1要增加到比它右面比它大的那一系列数中最小的那个数，这里并不冲突，因为我们在进行步骤1的时候，因为强调了最后一组a[i]<a[i+1]因此，在i位置之后，我们的排列一定是降序的，因此最后一个比a[i]大的数也一定是最小的。

代码实现

func CalAllPermutation(str string) string {

    // 记录首位置
    i := 0
    // 记录末位置
    j := 0
    for i = len(str) - 2; i >= 0; i-- {
        if str[i] <= str[i+1] {
            break
        }
    }
    if i < 0 {
        return str
    }
    //
    for j = len(str) - 1; j > i; j-- {
        if str[i] < str[j] {
            break
        }
    }
    str1 := []rune(str)
    // 交换
    str1[i], str1[j] = str1[j], str1[i]
    // 赋值
    str = string(str1)
    // 固定前面的字符串
    s := str[:(i + 1)]
    // 反转后面的字符串进行拼接
    s += ResverString(str[(i + 1):])
    return s

}
func ResverString(str string) string {
    r := []rune(str)
    j := len(r) - 1
    for i := 0; i < len(r)/2; i++ {
        r[i], r[j] = r[j], r[i]
        j--
    }
    return string(r)
}

参考

《编程之法：面试和算法心得》——作者：July