Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | 1x 1x 1x 1x 1x 1x 1x 8x 1x 1x 1x 173x 3x 3x 170x 170x 170x 170x 170x 170x 170x 173x 173x 173x 1x 1x 31x 2x 2x 29x 29x 29x 29x 29x 29x 29x 1x 4x 1x 1x 6x 1x 5x 5x 1x 4x 4x 4x 4x 5x 1x 4x 1x 3x 1x 2x | import {branch, of, type Branch, type Tree} from '#tree'
import {Number as ENumber} from '#util'
import {square} from '#Pair'
import {Array, pipe} from 'effect'
import type {NonEmptyArray} from 'effect/Array'
import {decode} from './decoder.js'
import {encode} from './encoder.js'
/**
* How many labeled trees of `n` nodes are there?
*
* https://en.wikipedia.org/wiki/Cayley%27s_formula
* @category codec
* @function
*/
export const labeledTreeCount = (n: number): bigint =>
BigInt(n) ** (BigInt(n) - 2n)
/**
* How many nodes in the tree generated by the given prüfer code?
* @category codec
* @function
*/
export const computeNodeCount = (code: number[]): number => code.length + 2
/** What is element count of the prüfer code for the given node count? */
export const codeCount = (nodeCount: number): number => nodeCount - 2
/**
* returns the prüfer sequence for the `nₜₕ` labeled tree with a node
* count of `nodeCount`. Note the `n` is an ordinal that starts at `1`.
* @category codec
* @function
*/
export const fromOrdinal = (n: bigint, nodeCount: number): number[] => {
if (nodeCount < 3) {
return []
}
const digits = Array.map(
ENumber.toRadix(n - 1n, nodeCount),
ENumber.increment,
),
padN = nodeCount - digits.length - 2
return pipe(
digits,
Array.prependAll(padN === 0 ? [] : Array.replicate(1, padN)),
)
}
/**
* Get the node count and index of the given prüfer code. This is the opposite of
* `ordinalToPrüfer` in that composing one of each in any order is identity.
* Returns a pair of node count and ordinal, where the ordinal is always smaller
* than the node count.
* @category codec
* @function
*/
export const toOrdinal: (
code: number[],
) => [ordinal: bigint, nodeCount: number] = code => {
if (code.length === 0) {
return [1n, 2]
}
const [lessOne, nodeCount] = pipe(
code,
Array.map(ENumber.decrement),
square.mapSecond(computeNodeCount),
)
return [ENumber.fromRadix(lessOne, nodeCount) + 1n, nodeCount]
}
/**
* Get the `nₜₕ` labeled numeric tree for the given node count.
* @category codec
* @function
*/
export const getNthTree = (ordinal: bigint, nodeCount: number): Tree<number> =>
pipe(fromOrdinal(ordinal, nodeCount), decode)
/**
* In the ordered set of trees with N labeled nodes, a set where the given tree
* is very much a member of, what is the ordinal number of the given tree in the
* set? Returns a numeric pair of ordinal and node tree count.
* @category codec
* @function
*/
export const treeToOrdinal: (
self: Branch<number>,
) => [ordinal: bigint, nodeCount: number] = branch =>
pipe(branch, encode(ENumber.Order), toOrdinal)
/**
* A list of all codes for the given node count.
*
* Above the node count of 36 returns an array with the first code only.
* @category codec
* @function
*/
export const allCodesAt = (nodeCount: number): NonEmptyArray<number[]> => {
const count = labeledTreeCount(nodeCount)
return nodeCount >= 36
? [fromOrdinal(1n, nodeCount)]
: pipe(
Array.range(1, Number(count)),
Array.map(n => fromOrdinal(BigInt(n), nodeCount)),
)
}
/**
* A list of all possible trees for the given node count.
* @category codec
* @function
*/
export const allTreesAt = (nodeCount: number): Tree<number>[] =>
nodeCount < 2
? []
: nodeCount === 2
? [branch(1, [of(2)])]
: pipe(nodeCount, allCodesAt, Array.map(decode))
|