CODEWITHSUNDEEP
javascriptarraysalgorithmdata-structuresecmascript-6
Tyler Evans
Tyler Evans

Reputation: 579

Two element combinations of an array javascript

If i have an array of letters, for example

['A','C','D','E']

and I wanted to find all the 2 letter combinations of this array, what is the best way of doing this without using 2 for loops. For example:

for (var i=0; i<arr.length;i++) {
  for (var j=i+1; j<arr.length;j++) {
    console.log(arr[i] + " " + arr[j]);
  }
}

The issue with this, is that if the array becomes massive (1000 elements), it usually times out. Is there another way (alternate data structure etc to do this)?

Upvotes: 0

Views: 787

Answers (4)

Luke Kot-Zaniewski
Luke Kot-Zaniewski

Reputation: 1161

I really beat this one into the ground. As expected, @Louis Durand 's answer of two nested for loops was fastest on an array containing 100 strings (around 4 ms on my machine). This shows that a nested loop is probably your best bet in this situation.

Second fastest is my recursive solution which did the same in around 7-8 ms.

Third was @Redu 's answer which clocked in around 12-15 ms for the same task. I suspect his implementation is slower because he uses slice method in his algo to update array (other answers just increment the index leaving the input array unchanged which is much faster). Also this implementation results in multiple copies of the input array being stored in memory (every time the function is called it creates a new input array from the original array from which it removes the first elelment). This could also potentially affect performance.

So to answer your question: no I don't think there is a much better approach to what you are doing other than concatenating onto string and printing answers at the very end (what Louis suggested).

    var arr = [];
    for (var i = 0; i< 100; i++){
        arr.push(i+"");
      }
 /*
    console.time("test0");
    test0();

    function test0() {
    var s = "";
    for (var i=0; i<arr.length-1;i++) {
      for (var j=i+1; j<arr.length;j++) {
        s += arr[i] + " " + arr[j]+" ; ";
      }
      s += "\n";
    }

    console.log(s);
    }
    console.timeEnd("test0"); 
*/
   
    console.time("test1"); 
    test1();
    function test1() {
    var output = [];
    getCombos(0, 0, [], 2);
    console.log(JSON.stringify(output));

     function getCombos(index, depth, tmp, k){
     if(depth < k){
         for(var i = index; i<arr.length; i++){
             var tmp1 =  [arr[i]];
             Array.prototype.push.apply(tmp1, tmp);
             getCombos(i+1, depth+1,tmp1, k);
           }
        }else{
             output.push(tmp);
          }
        }
    }
    console.timeEnd("test1");

        /*
        console.time("test2"); 
        test2();
        function test2(){
    Array.prototype.combinations = function(n){
      return this.reduce((p,c,i,a) => (Array.prototype.push.apply(p,n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
                                                                          : [[c]]),p),[]);

};

console.log(JSON.stringify(arr.combinations(2)));
    }

    console.timeEnd("test2");*/

Here is a recursive solution that doesn't solve your time complexity problem but is another way to consider. The added advantage is that you can generalize it to any k so you are not stuck finding only combinations of two letters. Also you only declare one loop (although more than one copy of it will exist in your call stack)

var arr = ["a", "b", "c", "d", "e"];
var output = "";
getCombos(0, 0, [], 2);
console.log(output);

 function getCombos(index, depth, tmp, k){
 if(depth < k){
     for(var i = index; i<arr.length; i++){
         var tmp1 =  [...tmp, arr[i]];
         getCombos(i+1, depth+1,tmp1, k);
       }
    }else{
         output += tmp.toString() + ";";
      }
    }

Upvotes: 1

Redu
Redu

Reputation: 26161

Not only two but with any number of elements you might do as follows;

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => [].concat(e,c))
                                                 : [[c]]),[]);
};

console.log(JSON.stringify([1,2,3,4,5,6].combinations(2)));
console.log(JSON.stringify([1,2,3,4,5,6].combinations(3)));

Well as per @Lucas Kot-Zaniewski's comments I have refactored my code to use .push() operations in the place of .concat() instructions and also where required a spread operation i did use Array.prototype.push.apply(context,[args]). These two changes made the code to run 2.5 ~ 3 times faster (resulting 3.5-7 msecs vs 9.5-19 msecs) when an input of 100 items array is given and a combination of two of each is requested. Yet once tried with 1000 items of 2 combinations the difference is more dramatic like 400ms vs 6000ms.

A test can be seen at https://repl.it/DyrU

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => (Array.prototype.push.apply(p,n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
                                                                      : [[c]]),p),[]);
};

console.log(JSON.stringify([1,2,3,4,5,6].combinations(2)));

Upvotes: 1

Louis Durand
Louis Durand

Reputation: 335

I think your code has a mistake cause here, E would never be used. It should rather be:

var s = "";
for (var i=0; i<arr.length-1;i++) {
  for (var j=i+1; j<arr.length;j++) {
    s += arr[i] + " " + arr[j]+" ; ";
  }
  s += "\n";
}
console.log(s);

Note that if you log everything in the console, it's no surprise that it times out.

Upvotes: 0

Gabriele Petrioli
Gabriele Petrioli

Reputation: 196002

Use the .map()

Something like this

var arr = ['A','C','D','E'],
    combinations = arr.map((v,i)=>arr.slice(i+1).map(v2=>v+v2));

console.log(combinations);

Although this code will also iterate twice over the elements. (it will actually perform worse than your code since map executes a function for each item and it also creates temporary array copies with the slice, so it is here just for an alternate approach, not a more performant.)

Upvotes: 2

Related Questions