Given an array write a function that returns all the possible triplets/sequences of that array? JavaScript

Question

For example, given A = [1, 2, 1, 1], the function should return 3.

Creates only three different sequences: (1, 2, 1), (1, 1, 1) and (2, 1, 1). The correct answer for this example is 3.

Given A = [1, 2, 3, 4], the function should return 4. There are four ways: (1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4).
Given A = [2, 2, 2, 2], the function should return 1. There is only one way: (2, 2, 2).
Given A = [2, 2, 1, 2, 2], the function should return 4. There are four ways: (1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2).
Given A = [1, 2], the function should return 0

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [1..N].

Here is my Brute Force Solution below!

I was wondering if anybody out there has a better more optimized solution?

Detected time complexity of this solution: O(N**3*log(N)) or O(N**4)

const theatreTickets = (array) => {
  let combos = []
  if(array.length < 2) {
    combos.length = 0
  }

  for(let i = 0; i <= array.length; i++) {
    for(let j = i + 1; j <= array.length - 1; j++) {
      for(let k = j + 1; k <= array.length - 1; k++) {
        combos.push([array[i], array[j], array[k]])
      }
    }
  }
  combos = Array.from(new Set(combos.map(JSON.stringify)), JSON.parse)
  return combos.length
}


console.log(theatreTickets([1, 2, 1, 1])) // Should Be 3

Thank you!

This is probably a better question for code review – Rashid 'Lee' Ibrahim Mar 22 '20 at 04:37 — Rashid 'Lee' Ibrahim, Mar 22 '20 at 04:37
Where would I ask this for code review? – Jonathan Aug 07 '20 at 01:53 — Jonathan, Aug 07 '20 at 01:53
https://codereview.stackexchange.com/ – Rashid 'Lee' Ibrahim Aug 07 '20 at 13:56 — Rashid 'Lee' Ibrahim, Aug 07 '20 at 13:56

score 2 · Accepted Answer · answered Mar 22 '20 at 05:11

I think you need to combine, algorithm of combination and unique. It will work. Sample is given below.

Source: Efficient algorithm to get the combinations of all items in object

function combine(items, numSubItems) {
        var result = [];
        var indexes = new Array(numSubItems);
        for (var i = 0 ; i < numSubItems; i++) {
            indexes[i] = i;
        }
        while (indexes[0] < (items.length - numSubItems + 1)) {
            var v = [];
            for (var i = 0 ; i < numSubItems; i++) {
                v.push(items[indexes[i]]);
            }
            result.push(v);
            indexes[numSubItems - 1]++;
            var l = numSubItems - 1; // reference always is the last position at beginning
            while ( (indexes[numSubItems - 1] >= items.length) && (indexes[0] < items.length - numSubItems + 1)) {
                l--; // the last position is reached
                indexes[l]++;
                for (var i = l +1 ; i < numSubItems; i++) {
                    indexes[i] = indexes[l] + (i - l);
                }
            }        
        }
        return result;
    }

    var combinations = combine([1,2,1,1], 3);
    console.log([...new Set(combinations.map(x => x.join(",")))]);
    combinations = combine([1,2,3,4], 3);
    console.log([...new Set(combinations.map(x => x.join(",")))]);

Thank you for this answer. I agree, finding an efficient combine algorithm without repeats would work. I tried a multiple pointers pattern but could not get that to work. So went with Brute Force solution. However, this code above, after running it, seems to have the same time complexity as the Brute Force Solution which is `Detected time complexity: O(N**3*log(N)) or O(N**4) ` — Jonathan, Mar 22 '20 at 17:22
nope! I dont think so! in this u have max O(N**2+...) complexity. — xdeepakv, Mar 22 '20 at 17:31
You are totally right. Sorry. I ran the code again and your solution is way faster! haha. Here is a benchmark test to prove. Link: (https://jsperf.com/combine/1) — Jonathan, Mar 22 '20 at 21:18

Given an array write a function that returns all the possible triplets/sequences of that array? JavaScript

1 Answers1