给定一个数组，写一个函数返回该数组所有可能的三元组/序列？Java Script语言

Question

例如，给定A=[1,2,1,1]，函数应该返回3。

仅创建三个不同的序列：（1,2,1）、（1,1,1）和（2,1,1）。此示例的正确答案是3。

>

给定A=[1,2,3,4]，函数应该返回4。有四种方式：（1,2,3），（1,2,4），（1,3,4）和（2,3,4）。

给定A=[2，2，2]，函数应该返回1。只有一种方法：（2，2，2）。

给定< code>A = [2，2，1，2，2]，该函数应该返回4。有四种方式:< code>(1，2，2)，(2，1，2)，(2，2，1)和(2，2，2)。

给定A=[1,2]，函数应该返回0

为以下假设编写有效的算法：

N是[0..100000]范围内的整数；数组A的每个元素都是[1..N]范围内的整数。

这是我下面的蛮力解决方案！

我想知道是否有人有更好，更优化的解决方案？

检测到此解决方案的时间复杂度：O（N**3* 对数（N））或 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

谢谢大家！

Answer 1

我认为你需要组合，算法的组合和唯一性。它会起作用的。示例如下。

来源：获取对象中所有项组合的高效算法

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(",")))]);