Improving the performance of a function that generates all possible combinations of elements within an array

Question

Improving the performance of a function that generates all possible combinations of elements within an array

After coming across this function online, I decided to optimize it.

For instance, if we have an input of [1, 2, 3], the corresponding output would be

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

Below is the code snippet:

const combinations = arr => {
  let parentValue = [];
  let cursor = 0;

  for (const parentThis of arr) {
    const value = [[parentThis]];
    for (const thiss of parentValue) {
      value.push(thiss.concat([parentThis]));
    }
    parentValue = parentValue.concat(value);
  }
  return parentValue;
};

(I apologize for the unconventional variable names; it's due to executing this as a MongoDB aggregation)

Executing this operation 10,000 times on an array consisting of 10 elements takes approximately 23 seconds. How can I enhance its performance? I'm willing to make some compromises.

One immediate enhancement I noticed was reducing the number of elements. When executed 10,000 times on an array with 9 elements, the time taken decreased to 9 seconds.

I suspect that rejecting certain outputs before they are created (such as single-element combinations and all-elements combinations which might not be very useful) could lead to further improvements, but I’m struggling to implement this in code.

I attempted to enhance the performance by eliminating the initial iteration (by providing [arr[0]] as the initialValue and commencing the outer loop from the second element), although it didn’t result in a noticeable difference.

javascript arrays algorithm performance

Answer 1

Answer №1

It takes approximately 1 second to run through 10,000 iterations on an array containing 10 elements.

function powerset(A){
  const n = A.length;
  const numSets = (1 << n) - 1;
  const result = new Array(numSets);

  for (let k=1; k<=numSets; k++){
    const set = [];
    result[k - 1] = set;
    let temp = k;
    let i = 0;
    while (temp){
      if (temp & 1)
        set.push(A[i]);
      temp >>= 1;
      i += 1;
    }
  }
  
  return result;
}


var A = [1,2,3,4,5,6,7,8,9,10];
var start = new Date;
for (let i=0; i<10000; i++)
  var t = powerset(A);
console.log((new Date - start) / 1000);

georg suggested in the comments under this answer that replacing

const result = new Array(numSets);

with const result = []; and changing the assignment to result.push(set); could potentially improve efficiency further. This was tested on node with array sizes ranging from 15-20.

Answer 2

It takes approximately 1 second to run through 10,000 iterations on an array containing 10 elements.

function powerset(A){
  const n = A.length;
  const numSets = (1 << n) - 1;
  const result = new Array(numSets);

  for (let k=1; k<=numSets; k++){
    const set = [];
    result[k - 1] = set;
    let temp = k;
    let i = 0;
    while (temp){
      if (temp & 1)
        set.push(A[i]);
      temp >>= 1;
      i += 1;
    }
  }
  
  return result;
}


var A = [1,2,3,4,5,6,7,8,9,10];
var start = new Date;
for (let i=0; i<10000; i++)
  var t = powerset(A);
console.log((new Date - start) / 1000);

georg suggested in the comments under this answer that replacing

const result = new Array(numSets);

with const result = []; and changing the assignment to result.push(set); could potentially improve efficiency further. This was tested on node with array sizes ranging from 15-20.

Answer 3

Answer №2

A slight nudge might be all that's needed to optimize the code.

// Instead of using concat method, try using the spread operator for better performance.
parentValue.push(...value);

Answer 4

A slight nudge might be all that's needed to optimize the code.

// Instead of using concat method, try using the spread operator for better performance.
parentValue.push(...value);

Improving the performance of a function that generates all possible combinations of elements within an array

Answer №1

Answer №2

Similar questions

Encountering an issue when running npm build on server

Is it considered poor practice to create refs outside of a component?

When the function is clicked, an error occurs that says: "return is a reserved word"

Ways to transfer a function as attributes from one functional element to another?

Need Root Directories in Browserify and Using NPM (eliminating the constant use of '../../../..' in both cases)

Tips for Managing the Hardware Back Button in Ionic 3

Struggling to find your way around the header on my website? Let me give

Even though I have successfully compiled on Heroku, I am still encountering the dreaded Application Error

JavaScript Language Conversion Templating

Invoke a React component within a conditional statement

The Forward and Back Buttons respond based on the current position of the caret

Implementing CSRF token for the current window's location

Encountering a tIDENTIFIER syntax error while trying to include a button_tag in Rails

Deactivate CS:GO Dedicated Server using Node.js child_process

Incorporate a new substance into a THREEJS Mesh

Transfer information via query or retrieve from storage in Vue

Tips for showcasing several images with accompanying content once the webpage has finished loading

The Express/Mongoose route consistently modifies the identical item

Using JavaScript and node.js, make sure to wait for the response from socket.on before proceeding

The output of jquery's val() function will not show the actual value