Поиск уникальных пар в массиве

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% медленнее