быстрый метод для создания анаграмм на JS без библиотек

#javascript

есть код для поиска анаграмм, получаю массив всех анаграмм, сортирую его и беру индекс
анаграмму из массива, которая соответствует исходному слову. Но есть проблема, для
длинных слов код работает очень медленно, может кто-то уже сталкивался с такой проблемой?
буду рад советам и помощи!

function listPosition(word) { 
 var arr = [word]; 
 var anagrams = {}; 
 arr.forEach(function(str) { 
 var recurse = function(ana, str) { 
  if (str === '') 
   anagrams[ana] = 1;
   for (var i = 0; i < str.length; i++)
   recurse(ana + str[i], str.slice(0, i) + str.slice(i + 1)); 
  }; 
   recurse('', str); 
}); 
  var result = Object.keys(anagrams); 
  return result.sort().indexOf(word) + 1; 
} 

console.log(listPosition('BOOKKEEPER'));

    

Ответы

Ответ 1

Для начала нужно научиться считать общее число анаграмм слова.
Потом можно рекурсивно считать количество лексикографически меньших анаграмм.



const fact = n => n<2?n:n*fact(n-1);

const wordletters = word => word.split('').sort()
  .reduce((res,letter) => 
    (res[letter]=(res[letter]|0)+1, res), {});

const objVals = obj => 
  Object.keys(obj)
    .map(key => obj[key]);

// Общее число всех анаграмм
// n! / (n₀!*n₁!*n₂!*...nₖ!)
const anaCount = word => 
  fact(word.length)
  /
  objVals(wordletters(word))
    .map(fact)
    .reduce((c, a) => c*a, 1);

const anaIndex = word => {
  let count = 0;
  let letters = Object.keys(wordletters(word)).sort();
  let index = letters.indexOf(word[0]);
  let lesser = letters.slice(0, index); // буквы меньшие первой
  lesser.forEach(letter => {
    // Считаем все, начинающиеся на letter
    let set = word.split('');
    // исключаем letter
    set.splice(set.indexOf(letter), 1);
    count += anaCount(set.join(''));
  });
  // рекурсия от слова без первой буквы
  if (word.length > 1) count += anaIndex(word.substr(1));
  return count;
};

console.log(anaCount('BOOKKEEPER'));       // 151200
console.log(anaIndex('BOOKKEEPER'));       // 10742
console.log(anaIndex('BOOKKEEPERMASTER')); // 10991405956




ES5