# environment setup

​

# this is CoffeeScript (http://coffeescript.org/)

# and I'm using the Underscore.js library (http://underscorejs.org/)

​

log = console.log

​

testFunctionUsingTestCases = (fun, funName, testCases) ->

  for testCase in testCases

    expectedResult = _(testCase).first()

    callArguments = _(testCase).rest()

    actualResult = fun.apply(undefined, callArguments)

    if ! _.isEqual(actualResult, expectedResult)

      log("test failed for function "+funName+" - arguments, expected, and actual:", callArguments, expectedResult, actualResult)

      return

  log("all tests passed for function "+funName)

​

​

# defining evaluatePermutation

​

absOfDifference = (num1, num2) ->

  Math.abs(num1 - num2)

​

# Big O: O(n) for n = permutation size

evaluatePermutation = (permutation) ->

  current = _(permutation).first()

  for number in _(permutation).rest()

    current = absOfDifference(current, number)

  return current

evaluatePermutationTestCases = [

  [1, [1]]

  [1, [1, 2]]

  [2, [1, 2, 3]]

  [2, [2, 1, 3]]

  [0, [3, 1, 2]]

  [0, [3, 2, 1]]

  [2, [1, 2, 3, 4]]

  [4, [1, 3, 2, 4]]

  [2, [2, 1, 3, 4]]

]

testFunctionUsingTestCases(evaluatePermutation, "evaluatePermutation", evaluatePermutationTestCases)

​

​

permute = `function(input) {

    var permArr = [],

    usedChars = [];

    function main(input){

        var i, ch;

        for (i = 0; i < input.length; i++) {

            ch = input.splice(i, 1)[0];

            usedChars.push(ch);

            if (input.length == 0) {

                permArr.push(usedChars.slice());

            }

            main(input);

            input.splice(i, 0, ch);

            usedChars.pop();

        }

        return permArr

    }

    return main(input);

};` # from http://stackoverflow.com/a/11509565/578288

​

# Big O: O(n)

setWithSize = (size) ->

  [1..size]

​

# Big O: O(n!)

permutationsOfSetWithSize = (size) ->

  return _.compose(permute, setWithSize)(size)

permutationsOfSetWithSizeTestCases = [

  [[ [1] ], 1]

  [[ [1, 2],[2, 1] ], 2]

  [[ [1, 2, 3],[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1, 2],[3, 2, 1] ], 3]

]

testFunctionUsingTestCases(permutationsOfSetWithSize, "permutationsOfSetWithSize", permutationsOfSetWithSizeTestCases)

​

​

# defining maximumValueForSetSize

​

# Big O: O(n*m) for n = num of permutations, m = permutation size

# evaluatePermutation is O(m)

# map is O(n)

# max is O(n)

maximumValueUsingPermutations = (permutations) ->

  return _.max( _(permutations).map(evaluatePermutation) )

​

# Big O: O(n!)

# maximumValueUsingPermutations is O(n^2)

# permutationsOfSetWithSize is O(n!)

maximumValueForSetSize = (size) ->

  return _.compose(maximumValueUsingPermutations, permutationsOfSetWithSize)(size)

maximumValueForSetSizeTestCases = [

  [1, 1]

  [1, 2]

  [2, 3]

]

testFunctionUsingTestCases(maximumValueForSetSize, "maximumValueForSetSize", maximumValueForSetSizeTestCases)

​

​

# defining maximumValuesForSetsUpTo

​

# Big O: O(n!)

maximumValuesForSetsUpTo = (maxSize) ->

  for size in [1..maxSize]

    maximumValueForSetSize(size)

maximumValuesForSetsUpToTestCases = [

  [[1, 1], 2]

  [[1, 1, 2], 3]

]

testFunctionUsingTestCases(maximumValuesForSetsUpTo, "maximumValuesForSetsUpTo", maximumValuesForSetsUpToTestCases)

​

​

# useful calculations

​

maxSize = 5

log("maximum values for sets of sizes up to #{maxSize}:", maximumValuesForSetsUpTo(maxSize) )

​

# this takes too long to run - estimated over a year

#idealSize = 2012

#log("maximum value for set of size #{idealSize}:",  maximumValueForSetSize(idealSize) )