[JS] Alphabetic Anagrams

description.txt

Task from Codewars: https://www.codewars.com/kata/53e57dada0cb0400ba000688/train/javascript

Consider a "word" as any sequence of capital letters A-Z (not limited to just "dictionary words"). For any word with at least two different letters, there are other words composed of the same letters but in a different order (for instance, STATIONARILY/ANTIROYALIST, which happen to both be dictionary words; for our purposes "AAIILNORSTTY" is also a "word" composed of the same letters as these two).

We can then assign a number to every word, based on where it falls in an alphabetically sorted list of all words made up of the same group of letters. One way to do this would be to generate the entire list of words and find the desired one, but this would be slow if the word is long.

Given a word, return its number. Your function should be able to accept any word 25 letters or less in length (possibly with some letters repeated), and take no more than 500 milliseconds to run. To compare, when the solution code runs the 27 test cases in JS, it takes 101ms.

For very large words, you'll run into number precision issues in JS (if the word's position is greater than 2^53). For the JS tests with large positions, there's some leeway (.000000001%). If you feel like you're getting it right for the smaller ranks, and only failing by rounding on the larger, submit a couple more times and see if it takes.

Python, Java and Haskell have arbitrary integer precision, so you must be precise in those languages (unless someone corrects me).

C# is using a long, which may not have the best precision, but the tests are locked so we can't change it.

Sample words, with their rank:
ABAB = 2
AAAB = 1
BAAA = 4
QUESTION = 24572
BOOKKEEPER = 10743

script.txt

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

// permutations with repetition
const countCombinations = (seq) => {
    const duplications = Object.values(
        seq.reduce((acc, e) => ({...acc, [e]: (acc[e] || 0) + 1}), {})
    ).reduce((acc, el) => acc * fact(el), 1);

    return fact(seq.length) / duplications;
};

// solution
function listPosition(s) {
    const arr = s.split('');
    let order = 1;

    for (let i = 0; i < arr.length; i++) {
        const set = new Set();
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i] && !set.has(arr[j])) {
                set.add(arr[j]);
                order += countCombinations([...arr.slice(i, j), ...arr.slice(j + 1)]);
            }
        }
    }

    return order
}


console.time('a');
console.log(listPosition('BAAA')); //4
console.log(listPosition('ABAB')); //2
console.log(listPosition('ABCD')); //1
console.log(listPosition('BCDA')); //10
console.log(listPosition('BDAC')); //11
console.log(listPosition('BDCA')); //12
console.log(listPosition('QUESTION')); //24572
console.log(listPosition('BOOKKEEPER')); //10743
console.timeEnd('a');

Hi, I'm trying to do this on codewars. I think I understand what you are doing with the "countCombinations" function. But I can get my head around your //solution portion. It would be a great help if you could explain what you are doing with the slices in the "listPosition" function. I looks like you are comparing letter values and checking if they are in a set, and if they pass you are slicing them, adding them to the "order" ,and passing them back to "countCombinations". I just don't understand why. It must have to do with the nature of permutations and their maths.

@Makebuildmodify, Not sure if it's the most efficient way to solve it, but the intention is like this.

After writing down all combinations in alphabetical order, it's possible to notice the pattern. We just need to calculate the number of combinations that are before the target word.

If we have the word "BDCA", then it will be placed after all combinations like:

"A [B, D, C]"
"_ A [C, D]"
"_ C [A, D]"
"_ _ A [C]"
"B D C A "

@mr-parus Thank you! That makes sense. This one took me about a week of evenings to solve. Primarily because I didn't understand the permutation formula.

Thank you! Your explanation was very helpful for me.