2b:null 2c:["$","title",null,{"children":"Superpermutations Graphs | Otávio Vasques | Observable"}] 31:T915,md`# Superpermutations Graphs Superpermutations are the subject of study of a very interesting problem of differents ways to [watch anime](https://en.wikipedia.org/wiki/Superpermutation#Lower_bounds,_or_the_Haruhi_problem). The superpermutation problem consists of fiding a string containing all permutations of ${tex`N`} symbols. One way to tackle the problem is to just brute force all permutations of the permutations, the problem with this approach is that you have to build ${tex`N!`} strings to find the minimal one. In practice is very hard to find the minimal one but there are other more efficient strategies to search for superpermutations. One of these alterntive approaches is to see the superpermutation problem as a graph problem, more preciselly a Traveler Salesperson Problem. We will build the graph with the permutations as the nodes and the number of character we need to append from one string to get to the other as the edges, I will call this as the append distance. This will be a graph will all possible edges present. Consider the permutations of 3 symbols: ${tex.block`ABC \quad ACB \quad BAC \quad BCA \quad CAB \quad CBA`} To get from ${tex`ABC`} to ${tex`BCA`} we just have to include an ${tex`A`} in the end. So we just need to add a single character to get from one permutation to the other. If we take the other direction, from ${tex`BCA`} to ${tex`ABC`} we need to add two characters: ${tex`BC`}. If we want to build the minimal string containing these two permutations it is better to go from ${tex`ABC`} to ${tex`BCA`}, and the final result will be ${tex`ABCA`} (4 characters of total length), than the other way around, which the result would be ${tex`BCABC`} (5 characters of total length). The superpermutation problem will be a Hamiltonian Path in this graph, i.e. a path that visits all nodes with the minimum length. With these approach multiple different heuristics can be applied to optimize the search, reducing the total time of search. The visualization bellow shows the graph for a superpermutaion problem of ${tex`N`} symbols, the colors represent the edges coming out of the nodes. *Actually the visualization is only pratical for ${tex`n=2`} and ${tex`n=3`}, with higher numbers it gets too cluttered. Please, if you are looking at it in your phone turn it sideways.*`32:Tee5,function permutationGraph(N) { const letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const perms = permutations(letters.slice(0, N)); const nodeColor = nodeColors(perms); const coordinates = equidistributionArcs(perms.length).map(coordinatesCircle(placementCircleRadius)); const permutationsCoords = permCoords(perms, coordinates); const vertices = Object.entries(permutationsCoords).map(x => { const label = x[0]; const coords = x[1]; const xC = coords[0]; const yC = coords[1]; const node = svg``; const labelSVG = svg`${label}`; return svg`${node} ${labelSVG}`; }) const links = []; const labels = []; for (var u of perms) { for (var v of perms) { if (u == v) continue; // const l = ({ // start: permutationsCoords[u], // end: permutationsCoords[v], // label: appendDistance(u, v) // }) const start = permutationsCoords[u]; const end = permutationsCoords[v]; const initialLengh = vectorNorm(vectorDiff(end, start)); // start const seDir = vectorDiff(end, start); const seNorm = vectorNorm(seDir); const unitSeDir = unitVector(seDir); var newStart = vectorAdd(start, vectorMultiply(unitSeDir, 1.5*nodeRadius)); // end const esDir = vectorDiff(start, end); const esNorm = vectorNorm(esDir); const unitEsDir = unitVector(esDir); var newEnd = vectorAdd(end, vectorMultiply(unitEsDir, 1.5*nodeRadius)); const label = appendDistance(u, v); var labelPos = vectorAdd(start, vectorMultiply(unitSeDir, 0.60*initialLengh)); //displacement var displacement = vectorMultiply(normalVector(seDir), 0.1*nodeRadius); if (u > v) { displacement = vectorMultiply(displacement, -1); } var newLabelPos = vectorAdd(labelPos, displacement); var newStart = vectorAdd(newStart, displacement) var newEnd = vectorAdd(newEnd, displacement) links.push(svg``); labels.push(svg`${label}`); } } return svg` ` }33:[] 2f:{"id":"481d3f54159c5ea9","slug":"superpermutations-graphs","title":"Superpermutations Graphs","thumbnail":"aa93dcdf9d16c2711fec8318906d9f4fe4eb88ff5b633debf199f0b20b6042fc","access_level":"public","create_time":"$D2020-05-02T14:23:23.102Z","update_time":"$D2020-05-18T01:56:06.022Z","view_time":null,"first_public_time":"$D2020-05-18T00:59:47.032Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"5e8d11e509318570","login":"otaviocv","name":"Otávio Vasques","avatar_url":"https://avatars-next.observableusercontent.com/21aa1d096ad0538e8d296d94b9560d33bcd6c2c7a3046310d200f7467de1e103","tier":"starter_2024"},"version":678,"publish_version":678,"role":null,"authored":false,"authors":[{"type":"individual","id":"67f6bc0db63009d0","login":"otaviocv","name":"Otávio Vasques","avatar_url":"https://avatars-next.observableusercontent.com/21aa1d096ad0538e8d296d94b9560d33bcd6c2c7a3046310d200f7467de1e103","tier":null}],"members":[{"type":"individual","id":"67f6bc0db63009d0","login":"otaviocv","name":"Otávio Vasques","avatar_url":"https://avatars-next.observableusercontent.com/21aa1d096ad0538e8d296d94b9560d33bcd6c2c7a3046310d200f7467de1e103","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Superpermutations Graphs","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"viewof nodeShrinker = slider({\n min: minNodeShrinker,\n max: maxNodeShrinker,\n step: 1,\n value: 30,\n title: \"Node size\",\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"viewof N = slider({\n min: 2,\n max: maxN,\n step: 1,\n value: 3,\n title: \"Permutations of how many symbols?\",\n description: \"Choose the number of elements to swap and build the superpemutation graph\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"permutationGraph(N)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"viewof maxN = number({title: \"Max N\", description: \"Warning! Big numbers of N take a lot to compute all permutations!\", value: 5})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":325,"value":"viewof maxNodeShrinker = number({title: \"Max Node Shrinker\", description: \"This may break the chart.\", value: 45})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"viewof minNodeShrinker = number({title: \"Min Node Shrinker\", description: \"This may break the chart.\", value: 5})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"md `---\n# Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"md `## Plot Config`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"margin = ({\n top: 30,\n bottom: 30,\n left: 30,\n right: 30\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"innerWidth = width - margin.left - margin.right","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":226,"value":"md`## Trigonometry`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"nodeRadius = Math.floor(width/(maxNodeShrinker - nodeShrinker + minNodeShrinker))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"placementCircleRadius = (innerWidth - 2*nodeRadius)/2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"function equidistributionArcs(N) {\n const circunference = 2*Math.PI\n var arcs = [];\n for (var i=0; i {\n return [r*Math.cos(theta), r*Math.sin(theta)]\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"md `## Vector Operations`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":409,"value":"function vectorDiff(p, q) {\n return [p[0] - q[0], p[1] - q[1]]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":413,"value":"function vectorAdd(p, q) {\n return [p[0] + q[0], p[1] + q[1]]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":445,"value":"function vectorNorm(v) {\n return Math.sqrt(v[0]**2 + v[1]**2);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":464,"value":"function vectorMultiply(v, a) {\n return [v[0] * a, v[1] * a];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":458,"value":"function unitVector(v) {\n const norm = vectorNorm(v);\n return [v[0]/norm, v[1]/norm];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":488,"value":"function normalVector(v) {\n if (v[1] != 0) {\n return unitVector([1, -v[0]/v[1]])\n } else {\n return unitVector([-v[1]/v[0], 1])\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"md `## Permutations Utilities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":383,"value":"function permCoords(perms, coordinates) {\n const permutationCoordinates = ({})\n for (var i=0; i< perms.length; i++) {\n const coords = coordinates[i]\n permutationCoordinates[perms[i]] = [width/2 + coords[0], width/2 + coords[1]];\n }\n return permutationCoordinates\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"function permutations(symbols) {\n if (symbols.length == 1) return [symbols];\n var allPermutations = [];\n for (var i=0; i symbol + x));\n }\n return allPermutations;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":566,"value":"nodeColors = perms => {\n const scale = d3.scaleBand().domain(perms).range([0,1]);\n return p => {\n return d3.interpolateSinebow(scale(p));\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":355,"value":"function appendDistance(p, q) {\n function rAppend(p, q, acc) {\n if (p == q) return acc;\n else return rAppend(p.slice(1,), q.slice(0,-1), acc + 1);\n }\n return rAppend(p, q, 0)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"md `## Other`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":248,"value":"zip = (arr, ...arrs) => {\n return arr.map((val, i) => arrs.reduce((a, arr) => [...a, arr[i]], [val]));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"md `---\n## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"import {number, slider, select} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"