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

Question

例如，给定A = [1, 2, 1, 1]，函数应该返回3。仅创建三个不同的序列：(1, 2, 1), (1, 1, 1) and (2, 1, 1). 这个例子的正确答案是3。给定A = [1, 2, 3, 4]，函数应该返回4。有四种方式：(1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4)。给定A = [2, 2, 2, 2]，函数应该返回1。只有一种方法：(2, 2, 2).给定A = [2, 2, 1, 2, 2]，函数应该返回4。有四种方式：(1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2)。给定A = [1, 2]，函数应该返回0为以下假设编写一个有效的算法：N 是 [0..100,000] 范围内的整数；数组 A 的每个元素都是 [1..N] 范围内的整数。下面是我的蛮力解决方案！我想知道是否有人有更好更优化的解决方案？检测到此解决方案的时间复杂度： O(N**3*log(N)) or O(N**4)

Answer 1

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 2

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

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