Skip to content

Instantly share code, notes, and snippets.

@milesrichardson
Last active June 26, 2018 11:42
Show Gist options
  • Save milesrichardson/8702c7c7725743e43cc6d82dd565cf23 to your computer and use it in GitHub Desktop.
Save milesrichardson/8702c7c7725743e43cc6d82dd565cf23 to your computer and use it in GitHub Desktop.
pairwise.js: Given a list, return a list of all pairs in that list via Array.reduce(). Optionally filter and transform (map) the pairs based on items and indices.

pairwise.js

pairwise(list, options)

Given a list, return a list of all pairs in that list via Array.reduce()

Optionally filter and transform (map) the pairs based on items and indices.

Arguments:

  • list (required): The input array
  • options (optional) -- See "Options" section for more details
    • filter: function to match pairs
    • map: function to transform pairs
    • limit: integer limit of pairs, or 0 for unlimited (default 0)
    • allowSelfPairs: boolean whether to allow self pairs (default false)

Examples:

  • Two-Sum from LeetCode: Find all pairs where left + right === target

    • https://leetcode.com/problems/two-sum/description/

    • Given an array of integers, return indices of the two numbers such that they add up to a specific target.

    • You may assume that each input would have exactly one solution, and you may not use the same element twice.

    const twoSum = (nums, target) =>
        pairwise(nums, {
            filter: ({ left, right }) => left + right === target,
            map: ({ leftIdx, rightIdx }) => [leftIdx, rightIdx],
            limit: 1,
            allowSelfPairs: false
        })[0]

Options:

{
    // filter: function({ left, right, leftIdx, rightIdx })
    //  Determine which pairs to include in output
    //
    // Given a pair { left, right, leftIdx, rightIdx }
    // Return true to include in output, false to exclude
    //
    // Default:
    filter = ({ left, right, leftIdx, rightIdx }) => true,

    // map: function({ left, right, leftIdx, rightIdx })
    //  Apply transformation to pairs before output
    //
    // Given a pair { left, right, leftIdx, rightIdx }
    // Return a transformed item for the output list
    //
    // Default:
    map = ({ left, right, leftIdx, rightIdx }) => ({
        left,
        right,
        leftIdx,
        rightIdx
    }),

    // limit: integer
    //  The maximum number of pairs to include, or 0 for no limit
    //
    // Default:
    limit = 0,

    // allowSelfPairs: boolean
    //  Whether to allow self pairs e.g. [1, 2, 3] -> (1,1), (2,2), ...
    //
    // Default:
    allowSelfPairs = false
}
const pairwise = (list, opts) => {
const {
filter = ({ left, right, leftIdx, rightIdx }) => true,
map = ({ left, right, leftIdx, rightIdx }) => ({
left,
right,
leftIdx,
rightIdx
}),
limit = 0,
allowSelfPairs = false
} = opts
var counter = 0
var hitLimit = false
const nextSliceIdx = leftIdx => (allowSelfPairs ? leftIdx : leftIdx + 1)
return list.reduce(
(pairs, left, leftIdx) =>
hitLimit
? pairs
: [
...pairs,
...list
.slice(nextSliceIdx(leftIdx))
.reduce((innerPairs, right, rightShift) => {
let rightIdx = nextSliceIdx(leftIdx) + rightShift
let match = filter({
left,
right,
leftIdx,
rightIdx
})
if (match) {
counter = counter + 1
if (limit > 0 && counter === limit) {
hitLimit = true
}
}
return !match
? innerPairs
: [
...innerPairs,
map({ left, right, leftIdx, rightIdx })
]
}, [])
],
[]
)
}
/*
Same function but synchronous
*/
const pairwiseSync = (list, opts) => {
const {
filter = ({ left, right, leftIdx, rightIdx }) => true,
map = ({ left, right, leftIdx, rightIdx }) => ({
left,
right,
leftIdx,
rightIdx
}),
limit = 0,
allowSelfPairs = false
} = opts
var counter = 0
var hitLimit = false
const length = list.length
const nextSliceIdx = leftIdx => (allowSelfPairs ? leftIdx : leftIdx + 1)
const pairs = []
for (let leftIdx = 0; leftIdx < length; leftIdx++) {
for (
let rightIdx = nextSliceIdx(leftIdx);
rightIdx < length;
rightIdx++
) {
let left = list[leftIdx]
let right = list[rightIdx]
let match = filter({ left, right, leftIdx, rightIdx })
if (!match) {
continue
}
pairs.push(map({ left, right, leftIdx, rightIdx }))
counter = counter + 1
if (limit > 0 && counter === limit) {
hitLimit = true
break
}
}
if (hitLimit) {
break
}
}
return pairs
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment