Страницы

Поиск по вопросам

среда, 13 марта 2019 г.

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

есть код для поиска анаграмм, получаю массив всех анаграмм, сортирую его и беру индекс анаграмму из массива, которая соответствует исходному слову. Но есть проблема, для длинных слов код работает очень медленно, может кто-то уже сталкивался с такой проблемой? буду рад советам и помощи!
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'));


Ответ

Для начала нужно научиться считать общее число анаграмм слова. Потом можно рекурсивно считать количество лексикографически меньших анаграмм.
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

Комментариев нет:

Отправить комментарий