字符串全排列

题目：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

关键词： 字典序， 所有排列。

字典序即排列组合中第一个不相同的元素应该符合该字符在字典中的先后顺序，这也是sort默认的排序，所以如果得到的全排列是无序的，使用sort()方法排序即可。

全排列是对不同元素交换顺序得到的，以'abc'为例，其排列类型可以有3!种，我们考虑其所有可能的排列方式时，通常会先固定第一个位置上的元素，然后对数组其余的元素进行排列，以此类推。

• 'a' + permutation('bc')
  --> 'a' + ('b' +permutation('c'), 'c' + permutation('b') ) ==> 'abc', 'acb'
• 'b' + permutation('ac') --> 'bac', 'bca'
• 'c' + permutation('ab') --> 'cab', 'cba'

假设数组起始位置为from_position， 终止位置为to_position。第一个位置可以选择放arr[i], i∈[from_position, to_position]，然后将arr[i]与arr[from_position]元素交换，保证刚选择的第i个元素位于该可选位置的数组最前，便于对数组余下位置j进行处理。余下的元素中，第二个位置可以选择arr[from_position+1]~arr[to_position]中的任意一个......即对某个数组中元素的全排列=固定第一个位置的所有选择*剩余位置的全排列

function Permutation(str) {
  if (str.length <= 1) {
    return str
  }
  let result = [];

  function realSort(strArr, from = 0, to = strArr.length - 1) {
    if (to <= 0) {
      return
    }
    if (from == to) {
      const res = strArr.join("")
      //注意去重，'aa'的全排列应该只有'aa'一种。
      if (!result.includes(res)) {
        result.push(res)
      }
    } else {
      for (let i = from; i <= to; i++) {
        swap(strArr, i, from);
        realSort(strArr, from + 1, to);
        swap(strArr, from, i);
      }
    }

  }

  function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp
  }


  realSort(str.split(""));
  return result.sort()
}

reference:
https://segmentfault.com/a/1190000002710424