作者:yanyige | 发布时间:2018-12-08 14:37

零、Source

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:

permutations('a'); // ['a']
permutations('ab'); // ['ab', 'ba']
permutations('aabb'); // ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

The order of the permutations doesn’t matter.

一、分析

分析输入，马上可以得出是一个全排列问题。需要注意的是，需要考虑到特殊情况，输入可能有相同的字符，eg 'aabb', 'aaaaaab'。

二、我的解法

let rec = new Array(100).fill(0);
function permutations(string) {
  let ret=[];
  permutate(ret, 0, [], string);
  return Array.from(new Set(ret));
}

function permutate(ret, len, mystr, string) {
  if (len === string.length) {
    ret.push(mystr.join(""));
    return mystr;
  } else {
    for(let i = 0;i < string.length; i ++) {
      if (rec[i] == 0) {
        mystr[len] = string[i]
        rec[i] = 1;
        permutate(ret, len + 1, mystr, string);
        rec[i] = 0;
      } 
    }
  }
}

三、大神，膜拜

function permutations(string) {
  var arr = string.split(''), tmp = arr.slice(), heads = [], out = [];
  if(string.length == 1) return [string];
  arr.forEach(function(v, i, arr) {
    if(heads.indexOf(v) == -1) {
      heads.push(v);
      tmp.splice(tmp.indexOf(v), 1);
      permutations(tmp.join('')).forEach(function(w) {out.push(v + w);});
      tmp.push(v);
    }
  });
  return out;
}

五行！！！

function permutations(string) {
  return (string.length == 1) ? [string] : string.split('').map(
     (e, i) => permutations(string.slice(0,i) + string.slice(i+1)).map((e2) => e+e2)
  ).reduce((r,e) => r.concat(e)).sort().filter((e,i,a) => (i==0) || a[i-1] != e);
}