Published
Edited
Apr 2, 2020
1 star
actuals = ns.map(n => ({ n, actual: theRealAnswer(n) }))
estimates = ns.map(n => ({ n, estimate: estimateExpectedNumberOfGroups(n) }))
/**
* Estimate the expected number of groups for a party of size N.
*/
function estimateExpectedNumberOfGroups(n, iterations = 2000) {
const groupCounts = range(iterations).map(() =>
countGroups(createPairsOfPeople(n))
);
return mean(groupCounts);
}
/**
* Given an array containing pairs of people, count the number of "groups" among them. This is done
* by treating the pair as an edge in a directed graph, and then counting the number of cycles in
* the graph.
*/
function countGroups(pairsOfPeople) {
let seen = new Set(),
groups = 0;
const digraph = DirectedGraph.fromEdges(pairsOfPeople);
for (const [person] of pairsOfPeople) {
if (seen.has(person)) {
continue;
}
const seenOnWalk = digraph.walkDfs(person);
seen = Sets.union(seen, seenOnWalk);
groups += 1;
}
return groups;
}
function createPairsOfPeople(n) {
const remainingPeople = new Set(range(n));
const pairsOfPeople = new Map();
for (let personA = 0; personA < n; personA++) {
const personB = selectRandomItem([...remainingPeople]);
remainingPeople.delete(personB);
pairsOfPeople.set(personA, personB);
}
return pairsOfPeople;
}
class DirectedGraph {
constructor() {
this.edges = new Map();
}
static fromEdges(edges) {
const digraph = new DirectedGraph();
for (const [frm, to] of edges) digraph.addEdge(frm, to);
return digraph;
}
addEdge(frm, to) {
let terminalNodes = this.edges.get(frm);
if (terminalNodes == null) {
terminalNodes = new Set();
this.edges.set(frm, terminalNodes);
}
terminalNodes.add(to);
}
walkDfs(source) {
const seen = this._dfsIter(source, new Set());
return new Set([...seen]);
}
*_dfsIter(source, seen) {
if (seen.has(source)) {
return;
}
seen.add(source);
yield source;
if (this.edges.has(source)) {
const targets = this.edges.get(source);
for (const target of targets.values()) {
yield* this._dfsIter(target, seen);
}
}
}
}
class Sets {
static union(a, b) {
return new Set([...a, ...b]);
}
}
height = 500
margin = ({ top: 20, right: 30, bottom: 30, left: 40 })
x = d3.scaleLinear()
.domain(d3.extent(estimates, d => d.n))
.range([margin.left, width - margin.right])
y = d3.scaleLinear()
.domain([0, d3.max(estimates, d => d.estimate)]).nice()
.range([height - margin.bottom, margin.top])
xAxis = g => g
.attr("transform", `translate(0,${height - margin.bottom})`)
.call(d3.axisBottom(x).ticks(width / 80).tickSizeOuter(0))
yAxis = g => g
.attr("transform", `translate(${margin.left},0)`)
.call(d3.axisLeft(y))
.call(g => g.select(".domain").remove())
.call(g => g.select(".tick:last-of-type text").clone()
.attr("x", 3)
.attr("text-anchor", "start")
.attr("font-weight", "bold")
.text("estimated number of groups"))
d3 = require("d3@5")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
