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 a bizarre npm issue while attempting to execute npm install for brain.js

create a JavaScript array variable for posting items

Error encountered when attempting to insert data into a PostgreSQL database using Node.js and Sequelize

Is it possible to determine the outcome of a JavaScript function using Python?

How can we determine in JavaScript whether a certain parameter constitutes a square number?

Ways to locate two div class elements that are generated dynamically

insert a new DOM element into an array using jQuery

There seems to be a problem with how the navbar is being displayed in ResponsiveSlides.js

Running a service in Express.js without being dependent on incoming requests

Python script using selenium webdriver to interact with an accordion container and expand its contents (round

Effortlessly move and rearrange various rows within an HTML table by utilizing JQuery alongside the <thead> elements

What is the best way to transform a list of Python+Flask objects into a list of JavaScript objects?

Ways to get a Discord bot to echo a message?

Creating components and dynamic routing based on the current route

When using QML, functions like Object.keys, Object.values, and JSON.stringify may return unexpected empty results

Utilizing React to highlight buttons that share the same index value upon hover

Reactjs - There was an error: $node.attr(...).tooltip is not defined

Manipulating object properties within an array through iteration

Encountering a TypeError when utilizing a npm hashtable within an object definition

When using React-hook-form, you need to tap twice to delete the last character in the input field, and double tap to enter the first