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