字符串的排列

题目描述

示例

代码

代码1 递归解法，每次固定一个值，然后交换其余字符顺序，逐步缩小规模

/*
递归
1. 递归的出口，只剩一个字符的时候，
2. 递归的循环过程，从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
 
注意：当有重复的字符时
 
假设1：（不可取）
如果一个数与后面的数字相同那么这两个数就不交换了。
例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
但是对bab，第二个数和第三个数不同，则需要交换，得到bba。
这里的bba和开始第一个数与第三个数交换的结果相同了，因此会有多余的结果，会多出不必要的递归，所以不可取。

假设2（可以）
换种思维，对abb，第一个数a与第二个数b交换得到bab，
然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
所以第一个数就不再用与第三个数交换了。
再考虑bab，它的第二个数与第三个数交换可以解决bba。
此时全排列生成完毕！

这样，我们得到在全排列中去掉重复的规则：
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。
*/
function Permutation(str)
{
    if(!str) return []
    
    let result = [] // 结果集
    
    let strArr = Array.from(str) // 字符串转数组
    
    dfs(strArr, 0, result)
    
    return result
    
    
    function dfs(arr, i, result){
        if(i === arr.length - 1){ // 如果是最后一位了
            result.push( arr.join('') )
            return;
        } 
        
        // 使用一个set记录是否有重复的值，
        // 比如 abb，第二次交换是 bab 第三次交换时，发现还是b，就不进行交换了
        let set = new Set()
        
        // for循环和swap的含义：对于“ABC”，
        // 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
        // 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
        // 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
        for( let j = i; j < arr.length; j++ ){
            if( !set.has(arr[j]) ){ // 使用set优化重复的情况
                set.add(arr[j])
                swap(arr, i, j)
                dfs(arr, i+1, result)

                // 用完之后再换回来
                // 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
                // 然后进行第三次交换，才能得到"CBA"
                swap(arr, j, i)
            }
        }
    }
    
    // 交换位置
    function swap(arr, i, j){
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
}

时间复杂度：O(n!),比如3个字符的全排列有6种

空间复杂度：O(1),原地交换

代码2 字典排序法，使用字典序全排列（先放一放，代码还没看太懂）

字典排序算法步骤。

我们先看一个例子。

示例： 1 2 3的全排列如下：

1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1

我们这里是通过字典序法找出来的。

那么什么是字典序法呢？

从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？

我们再来看一段文字描述：（用字典序法找124653的下一个排列）

你主要看红色字体部分就行了，这就是步骤。

如果当前排列是124653,找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数，

如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。

本例中将找到46,计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数，

本例找到的数是5，其位置计为j，将i与j所在元素交换125643,

然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列。

下图是用字典序法找1 2 3的全排列（全过程）：

总结得出字典排序算法四步法：

字典排序：

从右至左找第一个左邻小于右邻的数，记下位置i，值list[a]
从右边往左找第一个右边大于list[a]的第一个值，记下位置j，值list[b]
交换list[a]和list[b]的值
将i以后的元素重新按从小到大的顺序排列

举例：125643的下一个字典序列

右边值大于左边的3<4,4<6,6>5,则i=2，list[a]=5
从右往左找出第一个右边大于list[a]=5的值，找到6>5,j=3;list[b]=6;
交换list[a]和list[b]的值，序列125643->126543
将位置2以后的元素重新排序,126543->126345;
结束： 126345即125643的下一个序列

/*
字典排序
*/
function Permutation(str)
{
    if(!str) return []
    
    let result = [] // 结果集
    
    let strArr = Array.from(str) // 字符串转数组
    
    // 排序一下，从小到大
    strArr.sort()
    result.push( strArr.join('') ) // 第一个排序结果
    
    let len = strArr.length
    
    while(true){
        let lIndex = len - 1
        let rIndex
        
        // 从右至左找第一个左邻小于右邻的数
        while( lIndex >= 1 && strArr[lIndex-1] >= strArr[lIndex] ){
            lIndex--
        }
        
        // 如果全部找完，结束
        if( lIndex === 0){
            break;
        }
        
        rIndex = lIndex;
        
        // 找到最后一个比刚才值大的那个数
        while( rIndex < len && strArr[rIndex] > strArr[lIndex-1] ){
            rIndex++
        }
        
        // 交换位置
        swap(strArr, lIndex-1, rIndex-1)
        
        // 将剩余的排好序
        reverse(strArr, lIndex)
        
        // 记录结果
        result.push( strArr.join('') )
    }
    
    return result
    
    // 交换位置
    function swap(arr, i, j){
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
    
    function reverse(arr, k){
        if(arr.length <= k){
            return 
        }
        
        let len = arr.length
        
        for(let i = 0; i< Math.floor( (len-k)/2 ) ; i++){
            let m = k+i;
            let n = len -1 -i
            if(m<=n){
                swap(arr, m, n)
            }
        }
    }
}