recursion
We have the ability to implement the function generatePairs in a hopeful manner -
const generatePairs = (n = 0) =>
chooseN(2, range(0, n))
The function range is a basic one that creates an array from a to b -
const range = (a = 0, b = 0) =>
a > b
? []
: [ a, ...range(a + 1, b) ]
and chooseN is a general function that generates all combinations of size n from array a -
const chooseN = (n = 0, a = []) =>
n <= 0
? [[]]
: a.length <= 0
? []
: chooseN(n - 1, a)
.map(r => [a[0], ...r])
.concat(chooseN(n, a.slice(1))
You can see how generatePairs operates in your own browser below -
const range = (a = 0, b = 0) =>
a > b
? []
: [ a, ...range(a + 1, b) ]
const chooseN = (n = 0, a = []) =>
n <= 0
? [[]]
: a.length <= 0
? []
: chooseN(n - 1, a)
.map(r => [a[0], ...r])
.concat(chooseN(n, a.slice(1)))
const generatePairs = (n = 0) =>
chooseN(2, range(0, n))
const log = x =>
console.log(JSON.stringify(x))
log(generatePairs(3))
// [[0,0],[0,1],[0,2],[0,3],[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
log(generatePairs(2))
// [[0,0],[0,1],[0,2],[1,1],[1,2],[2,2]]
log(generatePairs(1))
// [[0,0],[0,1],[1,1]]
log(generatePairs(0))
// [[0,0]]
generators
Due to the large solution spaces involved in combinatorial problems, it is common practice to lazily generate combinations. JavaScript allows us to achieve this using generators -
const chooseN = function* (n = 0, a = [])
{ if (n <= 0)
return yield []
if (a.length <= 0)
return
for (const r of chooseN(n - 1, a))
yield [a[0], ...r]
yield* chooseN(n, a.slice(1))
}
Notice the structural similarity between this program and the previous one mentioned above -
const chooseN = function* (n = 0, a = [])
{ if (n <= 0)
return yield []
if (a.length <= 0)
return
for (const r of chooseN(n - 1, a))
yield [a[0], ...r]
yield* chooseN(n, a.slice(1))
}
For instance, we could create a solver function that identifies the first pair, [ a, b ] where a > 3 and 3*a equals 2*b. Importantly, no extra pairs will be generated after discovering the initial solution -
const solver = (size = 0) =>
{ for(const [a, b] of generatePairs(size))
if (a > 3)
if (3 * a === 2 * b)
return [a, b]
}
console.log(solver(10))
// [ 4, 6 ]
The solution with a = 4, b = 6 is accurate: 4 > 3 is true, and 3*4 equals 2*6 (12).
Below, we have the option to generate the entire array of pairs using Array.from -
const allPairs =
Array.from(generatePairs(3))
console.log(allPairs)
// [[0,0],[0,1],[0,2],[0,3],[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
Click on the snippet below to create pairs using JavaScript's generators -
const range = (a = 0, b = 0) =>
a > b
? []
: [ a, ...range(a + 1, b) ]
const chooseN = function* (n = 0, a = [])
{ if (n <= 0)
return yield []
if (a.length <= 0)
return
for (const r of chooseN(n - 1, a))
yield [a[0], ...r]
yield* chooseN(n, a.slice(1))
}
const generatePairs = (n = 0) =>
Array.from(chooseN(2, range(0, n)))
const log = x =>
console.log(JSON.stringify(x))
log(generatePairs(3))
// [[0,0],[0,1],[0,2],[0,3],[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
log(generatePairs(2))
// [[0,0],[0,1],[0,2],[1,1],[1,2],[2,2]]
log(generatePairs(1))
// [[0,0],[0,1],[1,1]]
log(generatePairs(0))
// [[0,0]]