[算法] 字符串全排列

[law-chain-hot]

字符串全排列

很好的图

步骤：

• 固定第一个字符，递归取得首位后面的各种字符串组合 （递归 part）
• 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合 (for循环 part)
• 同时判断 if (i == index || arr[i] !== arr[index])，如果交换的数的值不同，或者，i == idx，继续递归

回朔法

function swap(arr, x, y){
    var temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

//create the arr of result
var result = [];

//this is recursive fn
function getResult(arr, index){
    //base case
    if (arr.length-1 == index){
        result.push(arr.join(''));
        return;
    }
    
    // recursive part
    for (let i = index; i < arr.length; ++i){
        if (i == index || arr[i] !== arr[index]){
            swap(arr, index, i);
            getResult(arr, index+1);
            swap(arr, index, i);
        }

    }
}


// ------- test -------
function Permutation(str)
{
    // if empty
    if (!str) return [];

    // if not empty
    var arr = str.split("").sort();// convert into arr
    getResult(arr, 0);// return arr of result
    return result.sort();
}

console.log(Permutation('abc'));