# 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

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

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.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.