Repository navigation
Expand file tree
/
Copy path24.js
More file actions
53 lines (37 loc) · 1.44 KB
/
Copy path24.js
File metadata and controls
53 lines (37 loc) · 1.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
*/
var findMillionthPermutation = function(digits) {
digits = digits.split('').sort();
var result = [];
var factorial = function(num) {
if (num === 1) return 1;
if (num < 1) return 0;
return factorial(num - 1) * num;
}
var permutationsNeeded = 1000000,
permsAvailable = 0,
digitsLength = digits.length,
currentFactorial, stepsNeeded;
for (var i = 0; i < digitsLength - 1; i++) {
currentFactorial = factorial(digitsLength - i - 1);
stepsNeeded = 0;
permsAvailable = currentFactorial;
// Find lowest possible digit for this position
while (permsAvailable < permutationsNeeded) {
permsAvailable += currentFactorial;
stepsNeeded++;
}
// Establish digit
result.push(digits[stepsNeeded]);
digits.splice(stepsNeeded, 1)
// Adjust permutations needed
permutationsNeeded = permutationsNeeded - (permsAvailable - currentFactorial);
}
result.push(digits[0]);
return result.join('');
};
console.log(findMillionthPermutation('0123456789'));
// 2783915460