2
\$\begingroup\$

I was asked to solve a problem for \$\binom{n}{k}\$. I did the following implementation and am wondering if there's any feedback.

Input:

n = Integer

k = Integer

Output:

result = Array of arrays of integers

Constraints:

Time: \$O(\binom{n}{k})\$

Space: \$O(\binom{n}{k})\$

The order of the output array DOES NOT MATTER.

n and k are both positive.

Resources:

N Choose K

Combinations

function combinations(n, k) {
    let result= [];

  function recurse(start, combos) {
    if(combos.length === k) {
      return result.push(combos.slice());
    }
        // Check if you can actually create a combo of valid length
        // given current start number
        // For example: 5 choose 4 can't begin with [3] since it would never have 4 numbers
    if(combos.length + (n - start + 1) < k){
      return;
    }
    recurse(start + 1, combos);
    combos.push(start);
    recurse(start + 1, combos);
    combos.pop();
  }

  recurse(1, []);
  return result;
}

I was wondering if there's a reason why the time gets optimized using a backtracking solution.

// function combinations(n, k) {
//   let result = []
//   function combine(combo, currentNumber){
//     if(combo.length === k) {
//       result.push(combo);
//       return;
//     }
//     if(currentNumber > n) {
//       return;
//     }

//     let newCombo1 = combo.slice();
//     let newCombo2 = combo.slice();
//     newCombo2.push(currentNumber);

//     combine(newCombo2, currentNumber + 1);  
//     combine(newCombo1, currentNumber + 1);


//   }
//   combine([], 1);
//   return result;
// }

// speed: 1120.756 ms

//backtracking method
function combinations(n, k) {
  let result = []
  let stack = []
  function combine(currentNumber){
    if(stack.length === k) {
      let newCombo = stack.slice()
      result.push(newCombo);
      return;
    }
    if(currentNumber > n) {
      return;
    }

    stack.push(currentNumber)
    combine(currentNumber + 1);  
    stack.pop();
    combine(currentNumber + 1);
  }
  combine(1);
  return result;
}

console.time("Naive Combinations")
console.log(combinations(20, 10))
console.timeEnd("Naive Combinations")

// speed: 320.756 ms
\$\endgroup\$
  • 2
    \$\begingroup\$ The constraints are impossible using simple arrays: the size of the output is \$k\binom{n}{k}\$ which is not \$O\left(\binom{n}{k}\right)\$ \$\endgroup\$ – Peter Taylor Aug 1 '18 at 11:06
  • \$\begingroup\$ I was wondering why I am getting a better timing process for backtracking exercise solution \$\endgroup\$ – NinjaG Aug 1 '18 at 17:13
  • \$\begingroup\$ yeah. The output will be k ( n k). probably need to edit the question for big O. \$\endgroup\$ – NinjaG Aug 1 '18 at 17:14
2
+50
\$\begingroup\$

Performance testing.

Please note this answer is about performance not complexity.

Why the strange performance result?

The reason for the different results is down to poor testing.

JavaScript unlike most languages is never fully compiled. In the background there are multi level optimization engines that look at the running code and apply optimizations as the code is running.

The optimizer however has a penalty that is most evident when the code is first run. It can also optimize some code quicker than others.

To compare functions you need to let the optimizer do its thing (each browser have very different optimizing methods). Only after the function has been run several times can you start to get accurate results.

When I tested your code I found that the "backtracking" method was on average less than 5% slower.

Testing example

The snippet is a down and dirty performance tester that will test functions over many cycles and give a mean result of the function time.

Note that the result is not of a single call but that of many calls in a row. The tester will first make sure that the tests are not below the timer resolution before starting.

As an example I have kept the total test cycles low, but the numbers are still not stable and would take some more time before the optimizer is happy.

Included are your two functions as in the question, and alternative method using no recursive calls and a modification of one of your functions.

Performance increase.

In you function

function combinations(n, k) {
    let result= [];

  function recurse(start, combos) {
    if(combos.length === k) {
      return result.push(combos.slice());
    }
    if(combos.length + (n - start + 1) < k){
      return;
    }
    recurse(start + 1, combos);
    combos.push(start);
    recurse(start + 1, combos);
    combos.pop();
  }

  recurse(1, []);
  return result;
}

The combos array is being passed as an argument. There is no need to as it is the same array. Declare it outside the recurse function.

You are returning the array in one path and the other two your return undefined. Keep the return types the same.

You are recursing and then test for combos.length === k but you can test before the call saving the need to call.

There seams to be a slight favor for an arrow function, so changed the recurse function to such.

The modified function is consistently the quickest.

function combinationsAV2(n, k) {
  const result= [];
  const combos = [];
  const recurse = start => {
    if (combos.length + (n - start + 1) < k) { return }
    recurse(start + 1);
    combos.push(start);
    if(combos.length === k) {     
       result.push(combos.slice());
    }else if(combos.length + (n - start + 2) >= k){
       recurse(start + 1);
    }
    combos.pop();     
  }
  recurse(1, combos);
  return result;
}

Testing example

Note that the timing is adjusted to ensure good time resolution. The results are meaningless as absolute performance figures. They only have comparative meaning within a test run.

//n!/(r!(n-r)!)
Math.factorials = [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000];

Math.biCof = (n,r) => Math.factorials[n] / (Math.factorials[r] * Math.factorials[n-r]);

function combinationsG(n, k) {
    const result= [];
    const combo= [];
    const last = k - 1;  // points to last item in combo
    var i = k;
    while (i--) {
        combo.push(k - i);
    }
    const starts = [...combo];
    var pos,count = Math.biCof(n,k)
    while (count --) {
        result.push([...combo]);
        combo[last] += 1;
        if (combo[last] > n) {
            pos = 0;
            while (combo[last - pos] > n-pos) {
                pos += 1;
                combo[last-pos] += 1;
                if (pos === k) { break }
            }
            while (pos > 0) {
                combo[last-pos+1] = combo[last-pos] + 1
                pos --;
            }
        }
    }
    return result;
}

function combinationsAV2(n, k) {
  const result= [];
  const combos = [];
  const recurse = start => {
    if(combos.length + (n - start + 1) < k){
      return;
    }
    recurse(start + 1);
    combos.push(start);
    if(combos.length === k) {     
       result.push(combos.slice());
    }else if(combos.length + (n - start + 2) >= k){
       recurse(start + 1);
    }
    combos.pop();     
  }
  recurse(1, combos);
  return result;
}


function combinationsA(n, k) {
    let result= [];

  function recurse(start, combos) {
    if(combos.length === k) {
     
      return result.push(combos.slice());
    }

    if(combos.length + (n - start + 1) < k){
      return;
    }
    recurse(start + 1, combos);
    combos.push(start);
    recurse(start + 1, combos);
    combos.pop();
  }
  recurse(1, []);
  return result;
}

//backtracking method
function combinationsB(n, k) {
  let result = [];
  let stack = [];
  function combine(currentNumber){
    if(stack.length === k) {
      let newCombo = stack.slice();
      result.push(newCombo);
      return;
    }
    if(currentNumber > n) {
      return;
    }

    stack.push(currentNumber);
    combine(currentNumber + 1);  
    stack.pop();
    combine(currentNumber + 1);
  }
  combine(1);
  return result;

}


/*===========UTIL to display results============*/
function log(data) {
     const div = document.createElement("div");
     div.textContent = data;
     logger.appendChild(div);
}
log.clear = function(){ logger.innerHTML = "" }


/*================TESTING CODE==================*/
const tests = {
    data : [15,3],  // arguments for function calls
    functions : [ {  // functions to test and a name as reference
            name : "Backtracking method",
            func : combinationsB,
        },{
            name : "Native Combinations",
            func : combinationsA,
        },{
            name : "Modified Native",
            func : combinationsAV2,
        },{
            name : "While loops",
            func : combinationsG,
        },
    ],
    cycles : 100,
    prepCycles : 30, // Number of cycles to run before testing. This
                     // is a optimizer shake down and use to ensure test times
                     // are above the timerResolution
    testPerCycle : 20, 
    timedCycleTrim : 1,  // used to increase runtime if time to low
    timedCycles : 2,  // number of calls to test function * timedCycleTrim
    timerResolution : 0.4, // this is the minimum resolution of the timer in ms
                           // Note that due to security concerns performance timers
                           // have had the time resolution reduced to stop
                           // code attempting to access CPU caches
    testInterval : 10, // Time between test cycles. 
    resolutionError : false, // If the run time of the timedCycles is lower than
                             // the timer resolution then the accumulating error
                             // makes results meaningless. This flag is set true
                             // when test time is too small. In the prep phase
                             // timedCycleTrim is used to increase the time
                             // till a time above timerResolution is found

}

log.clear()
startTest(tests);


function startTest(tests){

    function doCycle(test){
        var totalTime, count, time, j, i;
        const data = tests.data;
        i = tests.testPerCycle;
        totalTime = count = 0;
    
        while (i--) {
            j = tests.timedCycles * tests.timedCycleTrim;
            
            /* ========= TEST LOOP ==========*/
            const now = performance.now();
            while (j --) { test.func(...data) }
            time =  performance.now() - now;
            
            
            if (time <= tests.timerResolution) {
                tests.resolutionError = true;
                return;
            }
            count ++;
            totalTime += time;
        }
        test.count += count;
        test.time += totalTime;
        test.mean = test.time / test.count;

    }
    function resetTest(test){
        test.count = 0;
        test.time = 0;
    }
    function showTestStatus(test) {
        if (test.count) {
            log(`Test '${test.name}' mean ${test.mean.toLocaleString(undefined,numFormat)}ms`);
           // log(`Total ${test.time.toLocaleString(undefined,numFormat)}ms over ${test.count} cycles`);
        } else {
            log(`Test '${test.name}' not yet tested`);
        }
    }
    function eachTest(call,testArr = tests.functions){
        testArr.forEach(call)
    }
    const selectors = {
        index : 0,
        random() { return tests.functions[Math.random() * tests.functions.length | 0] },
        ordered() { return tests.functions[(selectors.index++) % tests.functions.length ] }, 
    }
    function setupPrep() {
        selectors.index = 0;
        cycles = tests.prepCycles * tests.functions.length;
        selector = selectors.ordered;
        prepPhase = true;        
        tests.resolutionError = false;
        eachTest(resetTest);
        setTimeout(doNextCycle, tests.testInterval);
    }

    function doNextCycle() {
        const test = selector();
        doCycle(test)
        cycles --;
        if (tests.resolutionError) {
            if (prepPhase) {
                if (tests.timedCycleTrim  === 100) {
                    log(`Test '${test.name}' is not responding to cycle trim. Test aborted` );
                } else {
                    tests.timedCycleTrim += 2;
                    log(`Timed cycles increased to : ${tests.timedCycles * tests.timedCycleTrim}` );
                    setupPrep();
                }
            } else {
                log(`'${test.name}' failed, function runtime too low. Test aborted.` );
            }
        } else {
            if (cycles) {
                if (!prepPhase) { 
                    log.clear();
                    log(`Test status ${cycles / (tests.cycles * tests.functions.length) * 100 | 0}%`);
                    eachTest(showTestStatus);
                }
                setTimeout(doNextCycle, tests.testInterval);
            } else if (!prepPhase) {
                log.clear();
                log("Testing complete...");
                log("Calls per cycles : " + tests.timedCycles * tests.timedCycleTrim);
                log("----------------------------------------");
                eachTest(showTestStatus,[...tests.functions].sort((a, b) => a.mean - b.mean));
            } else {
                log("Prep complete...")
                prepPhase = false;
                cycles = tests.cycles * tests.functions.length;
                selector = selectors.random;
                eachTest(resetTest);
                setTimeout(doNextCycle, tests.testInterval);
            }
        }
    }
    const numFormat = {minimumFractionDigits: 3, maximumFractionDigits: 3};
    var cycles, selector, prepPhase;
    log("Starting tests. Calibrating run times... ");
    setupPrep();       
}
<code id="logger"></code>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.