在数组中查找唯一对

Question

鉴于此输入[3,1,2]我想要这个输出[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 3, 3 ] ]

它独特的对（[1,2] == [2,1]）

目前我已经做到了

const arr = [3,1,2];
const pairBuilder = (left, index, collection) =>
  collection.slice(index).map(right => [left, right]);

const pairs = arr.sort().flatMap(pairBuilder);
console.log(pairs)

这段代码很实用，但我想知道是否有更好的方法（在性能方面）来实现这个目标？我虽然使用lodash来改进排序/映射（使用chain），但我的问题更多是关于算法改进。

Answer 1

您可以使用带有Generator的function*并对数组进行切片以获得唯一的对。

function* getPairs(array, left) {
    var i = 0;
    while (i < array.length) {
        if (left) yield [left, array[i]];
        else yield* getPairs(array.slice(i), array[i]);
        i++;
    }
}

var array = [1, 2, 3];

console.log([...getPairs(array)]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

一种经典的方法。

function getPairs(array) {
    var i, j, result = [];
    for (i = 0; i < array.length; i++) {
        for (j = i; j < array.length; j++) {
            result.push([array[i], array[j]]);
        }
    }
    return result;
}

var array = [1, 2, 3];

console.log(getPairs(array));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

这是一种天真而缓慢的方法。但我相信它比问题中接受的答案和答案更快。它产生的新对象开销较少，并且需要较少的内存。朴素算法不使用递归。所以不会面临递归限制（默认为50）而且我相信它仍然可读且易于理解

        const inp = [3, 1,2];

        function genPair(inp) {
            const length = inp.length;
            const sorted = inp.sort();
            const result = [];
            for (let i = 0; i < length; i++) {
                for (let j = i; j < length; j++) {
                    result.push([sorted[i], sorted[j]]);
                }

            }
            return result;
        }
        const r = genPair(inp);
        console.log(r);

链接到js perf https://jsperf.com/find-dups/1在IE11中接受的答案慢60％，在Chrome中慢10％