Programming assignment №2

task_numbers.js

'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])