Instantly share code, notes, and snippets.

Last active June 26, 2018 11:42
Show Gist options
• 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
}```
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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 }) ] }, []) ], [] ) }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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 }