Skip to content

Instantly share code, notes, and snippets.

@mvasilkov
Last active February 11, 2020 15:38
Show Gist options
  • Save mvasilkov/feb657027434a9573587199d0d0ec7d1 to your computer and use it in GitHub Desktop.
Save mvasilkov/feb657027434a9573587199d0d0ec7d1 to your computer and use it in GitHub Desktop.
Programming assignment №2
'use strict'
/**
* Write a function that given a list of non negative integers,
* arranges them such that they form the largest possible number.
* For example, given [50, 2, 1, 9], the largest formed number is 95021.
*/
/* 1. Straightforward solution: get all permutations of numbers.
* Then find the largest of those.
* Run time: O(N!) */
function allPermutations(numbers) {
// Says if a number is in use
const usedNumbers = Array(numbers.length).fill(false)
let currentResult = numbers.map(n => '' + n).join('')
const resultLength = currentResult.length
// A recursive function for permutations
function p(result) {
// Found a permutation
if (result.length === resultLength) {
console.log('Comparing:', result)
// Check if this result is better than the old one
if (+result > +currentResult) currentResult = result
return
}
// Building a permutation: try to append all numbers...
for (let n = 0; n < numbers.length; ++n) {
// ...except for those that are already used.
if (usedNumbers[n]) continue
// Put the number in used numbers, then recur.
usedNumbers[n] = true
p(result + numbers[n])
usedNumbers[n] = false
}
}
p('')
console.log('Result:', currentResult)
}
allPermutations([50, 2, 1, 9])
console.log('---')
/* 2. Better solution: observe that lexicographical sort does exactly
* what we need. Run time: O(N log N) */
function betterSolution(numbers) {
console.log('Better result:', numbers
.map(n => '' + n)
.sort((a, b) => ('' + b + a).localeCompare('' + a + b, 'en'))
.join(''))
}
betterSolution([50, 2, 1, 9])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment