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

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, 2]，该函数应返回 1。只有一种方式:(2, 2, 2)。

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

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

为以下假设编写一个有效的算法:

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

下面是我的暴力解决方案!

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

检测到该解决方案的时间复杂度:O(N**3*log(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

我认为你需要结合，结合的算法和独特的。它会起作用的。下面给出了示例。

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