Project Euler - Problem 24: Lexicographic permutations

Tell us what’s happening:
I have no clue why my results are slightly different from expected results.

  **Your code so far**
const factorial = (num) => {
  if (num === 0) {return 1;}
  let factor = num;
  let result = 1;
  while (factor > 0) {
      result *= factor;
      factor--;
  }
  return result;
}

const lexicographicPermutations = (n) => {

let digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let result = "";
let len = digits.length;

while (len > 0) {
  let nextIndexDigit = Math.ceil(n / factorial(len - 1)) - 1;
  result += digits[nextIndexDigit];
  digits = digits.filter(el => el != digits[nextIndexDigit]);
  n = n % factorial(len - 1);
  // edge CASE
  if (n === 0) {
    return Number(result + digits.reverse().join(''));
  }
  len = digits.length;
}
return Number(result);
}

console.log('CASE ', 699999, 'result:', lexicographicPermutations(699999), 'expected: ', 1938246570);
console.log('CASE ', 899999, 'result:', lexicographicPermutations(899999), 'expected: ', 2536987410);
console.log('CASE ', 900000, 'result:', lexicographicPermutations(999999), 'expected: ', 2537014689);
console.log('CASE ', 699999, 'result:', lexicographicPermutations(999999), 'expected: ', 2783915460);

/*
CASE  699999 result: 1938246507 expected:  1938246570
CASE  899999 result: 2536987401 expected:  2536987410
CASE  900000 result: 2783915406 expected:  2537014689
CASE  699999 result: 2783915406 expected:  2783915460
*/

I build the whole solution for this problem with reduced size: for digits = [0, 1, 2, 3].
I did it in order to have some playground for developing and testing which is not so big as in original problem.
And I am getting correct results there, using exact same logic, see below:

const factorial = (num) => {
    if (num === 0) {return 1;}
    let factor = num;
    let result = 1;
    while (factor > 0) {
        result *= factor;
        factor--;
    }
    return result;
}

const nthPermutation = (n) => {
  
  let digits = [0, 1, 2, 3];
  let result = "";
  let len = digits.length;
  
  while (len > 0) {
    let nextIndexDigit = Math.ceil(n / factorial(len - 1)) - 1;
    result += digits[nextIndexDigit];
    digits = digits.filter(el => el != digits[nextIndexDigit]);
    n = n % factorial(len - 1);
    // edge CASE
    if (n === 0) {
      return result + digits.reverse().join('');
    }
    len = digits.length;
  }
  return Number(result);
}

//TESTING

//*********helper func for generating testCases
// const allPerms = (str) => {
//   let result = [str[0]]
//   for (let i = 1; i < str.length; i++) {
//     let newPerms = [];
//     for (let perm of result) {
//       for (let j = 0; j <= perm.length; j++) {
//         newPerms.push(perm.slice(0, j) + str[i] + perm.slice(j))
//       }
//     }
//     result = newPerms;
//   }
//   return result;
// }
// console.log(allPerms('0123').sort().map((el, idx) => [el, idx + 1]));
//*********



const testCases = [
  [ '0123', 1 ],  [ '0132', 2 ],
  [ '0213', 3 ],  [ '0231', 4 ],
  [ '0312', 5 ],  [ '0321', 6 ],
  [ '1023', 7 ],  [ '1032', 8 ],
  [ '1203', 9 ],  [ '1230', 10 ],
  [ '1302', 11 ], [ '1320', 12 ],
  [ '2013', 13 ], [ '2031', 14 ],
  [ '2103', 15 ], [ '2130', 16 ],
  [ '2301', 17 ], [ '2310', 18 ],
  [ '3012', 19 ], [ '3021', 20 ],
  [ '3102', 21 ], [ '3120', 22 ],
  [ '3201', 23 ], [ '3210', 24 ]
];

for (let test of testCases) {
  console.log('CASE  ', test[1]);
  console.log('Expected', test[0]);
  console.log('Result', nthPermutation(test[1]));
  console.log('-------------------');
}

/*OUTPUT
CASE   1
Expected 0123
Result 0123
-------------------
CASE   2
Expected 0132
Result 0132
-------------------
CASE   3
Expected 0213
Result 0213
-------------------
CASE   4
Expected 0231
Result 0231
-------------------
CASE   5
Expected 0312
Result 0312
-------------------
CASE   6
Expected 0321
Result 0321
-------------------
CASE   7
Expected 1023
Result 1023
-------------------
CASE   8
Expected 1032
Result 1032
-------------------
CASE   9
Expected 1203
Result 1203
-------------------
CASE   10
Expected 1230
Result 1230
-------------------
CASE   11
Expected 1302
Result 1302
-------------------
CASE   12
Expected 1320
Result 1320
-------------------
CASE   13
Expected 2013
Result 2013
-------------------
CASE   14
Expected 2031
Result 2031
-------------------
CASE   15
Expected 2103
Result 2103
-------------------
CASE   16
Expected 2130
Result 2130
-------------------
CASE   17
Expected 2301
Result 2301
-------------------
CASE   18
Expected 2310
Result 2310
-------------------
CASE   19
Expected 3012
Result 3012
-------------------
CASE   20
Expected 3021
Result 3021
-------------------
CASE   21
Expected 3102
Result 3102
-------------------
CASE   22
Expected 3120
Result 3120
-------------------
CASE   23
Expected 3201
Result 3201
-------------------
CASE   24
Expected 3210
Result 3210
-------------------
*/

So maybe I messed up in building tests? Doesn’t look like it. Or I misunderstood the task, I can’t figure it out.

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.0.0 Safari/537.36

Challenge: Project Euler - Problem 24: Lexicographic permutations

Link to the challenge:

This line is one issue. Why ceil instead of floor?

Good question actually.
I was playing around this division n / factorial(len - 1) and figured out that ceil gives me numbers I need. I didn’t try alternatives with floor yet.

ok, i used insted of line you mentioned, this one:

let nextIndexDigit = Math.floor(n / factorial(len - 1))

Now I am getting only one failed test in FCC console:

lexicographicPermutations(900000)
should return 2537014689.

But in my own smaller version of problem I am getting all incorrect results with this line.
I feel like I misunderstood some nuances here, in the task itself. Not sure which ones.

MAJOR update
AAAND I commented out this stuff:

// edge CASE
    // if (n === 0) {
    //   return Number(result + digits.reverse().join(''));
    // }

and passed all the tests.
Solved, but still feels strange :upside_down_face:

So it appears I accidentally built slightly different problem for digits =[ 0, 1, 2, 3]

So >>> two slightly different problems >>> two slightly different solutions.
Anyway, I guess I figured ‘main lesson’ of this challenge - play around factorials when dealing with number of permutations.