31:[{"id":"4b5ba719ca219115da1f182b89c4f2c26a46307c98de09f06e91c889969dc404e921d4cfc9dc94f42dc18fbc53b51431967c77678f3aa23aea4960a95a20a224","href":"https://static.observableusercontent.com/files/4b5ba719ca219115da1f182b89c4f2c26a46307c98de09f06e91c889969dc404e921d4cfc9dc94f42dc18fbc53b51431967c77678f3aa23aea4960a95a20a224","name":"permute-chairs.png","type":"image/png","lastModified":1617999361870.859,"size":9464}] 2f:{"title":"Ranking Permutations","cells":[{"id":0,"value":"md`# Ranking Permutations\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"md`

6 ways to permute 3 chairs - But how to rank these permutations ? 🤔

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":269,"value":"md`Based on paper [Ranking and Unranking Permutations in Linear Time](http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/RankPerm.html) by Wendy Myrvold and Frank Ruskey, Department of Computer Science, University of Victoria, Canada.\n\nNote that this is the fastest algorithm to rank/unrank permutations. But it does not rank them in lexicographic order, like for example [Lehmer code](https://en.wikipedia.org/wiki/Lehmer_code), which can be implemented in ${tex`\\mathcal{O}(n\\log{n})`} at best.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":75,"value":"viewof N_items = Range([3, 9], { step: 1, value: 5, label: 'Nb Items' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"md`There are ${fact(N_items).toLocaleString(\n 'en'\n)} permutations of ${N_items} items.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"viewof permNo = Range([0, fact(N_items)], {\n step: 1,\n value: 0,\n label: 'Permutation Rank'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":87,"value":"md`Permutation **[${perm.join(',')}]** is ranked **${permNo.toLocaleString(\n 'en'\n)}** / ${(fact(N_items) - 1).toLocaleString('en')}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":233,"value":"{\n const arr = allPerms\n .slice(0, -1)\n .map((e, i) => ({ rank: i, permutation: e.join(', ') }));\n return Table(arr, {\n align: { rank: 'left' },\n width: { rank: ' 10%', permutation: '90%' }\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":249,"value":"md`*Rank-Permutation(${N_items}) map*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":89,"value":"perm = unrank(permNo, N_items)","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"allPerms = d3.range(fact(N_items)).map(i => unrank(i, N_items))","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"md`The point of \\`rank\\`/\\`unrank\\` functions is to provide a fast two-way mapping between a permutation and its rank. Why they work is not obvious and explained in the paper above. But it is easy to check they do.\n\n#### Check \\`rank()\\` reaches all permutations:\n+ Are all generated permutations distinct ? ${allDistinct}\n+ Is the number of permutations equal to ${tex`${N_items}!`} ? ${allPerms.length ===\n fact(N_items)}\n\n#### Check \\`unrank()\\` is the inverse of \\`rank()\\` for all permutations:\n+ Is \\`unrank(rank(i))\\` for all \\`i\\` ? ${allCheckInv}\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"allDistinct = new Set(buildAllPerms(N_items).res.map(e => e.join('-'))).size ===\n fact(N_items)","pinned":false,"hidden":false,"mode":"ojs"},{"id":321,"value":"allCheckInv = d3\n .range(N_items)\n .map(i => rank(unrank(i, N_items)) === i)\n .every(e => e)","pinned":false,"hidden":false,"mode":"ojs"},{"id":97,"value":"md`### Two way example\n\n+ *Forward*: Sample permutation p = **[${p1.join(\n ','\n)}]** maps to rank r1 = **${r1.toLocaleString()}**.\n+ *Backward*: Rank r1 = **${r1.toLocaleString()}** maps back to permutation p2 = **[${p2.join(\n ','\n)}]**.\n\nAre p1 and p2 the same ? ${perm12Equal}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":99,"value":"{\n const s = p1\n .slice()\n .sort(d3.ascending)\n .join('-');\n const valid = s === d3.range(p1.length).join('-');\n\n const status = valid ? \"valid\" : \"invalid\";\n const text = `permutation p1 = **[${p1.join(',')}]** is ${status}`;\n const symbol = valid ? `👍🏼` : '👎🏼';\n const bg = valid ? `palegreen` : `lemonchiffon`;\n\n return md`

${symbol} ${text}

`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"p1 = [2, 5, 0, 6, 3, 4, 1]","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"md`*Change permutation \\`p1\\` above*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"r1 = rank(p1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":162,"value":"p2 = unrank(r1, p1.length)","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"perm12Equal = d3\n .zip(p1, p2)\n .map(([a, b]) => a === b)\n .every(e => e)","pinned":false,"hidden":false,"mode":"ojs"},{"id":109,"value":"md`### Generate all permutations\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":111,"value":"viewof N_items_2 = Range([3, 10], { step: 1, value: 8, label: 'Nb Items' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"md`Two ways to generate all permutations:\n+ Using the Myrvold-Ruskey \\`unrank\\` function\n+ Using [Heap's algorithm](http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf) - the fastest known\n\nAs expected for large numbers for permutations the \\`unrank\\` function is a bit slower.\n\n| Method | Myrvold-Ruskey | Heap |\n| :--- | :----: | ---: |\n| Nb permutations | ${allPermsMR.res.length.toLocaleString()} | ${allPermsMR.res.length.toLocaleString()} |\n| Time (ms) | ${allPermsMR.dt.toLocaleString()} | ${allPermsH.dt.toLocaleString()} |\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"allPermsMR = buildAllPerms(N_items_2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":117,"value":"allPermsH = buildAllPermsHeap(N_items_2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"md`### Iterate\n\nHere is an iterator over the permutations generated by the Lehmer functions.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"viewof N_items_3 = Range([3, 6], { step: 1, value: 6, label: 'Nb Items' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":123,"value":"iterPerm(N_items_3)","pinned":false,"hidden":false,"mode":"ojs"},{"id":125,"value":"md`## Implementation\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":136,"value":"function* iterPerm(N) {\n for (const i of d3.range(fact(N))) {\n const perm = unrank(i, N);\n yield perm;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"buildAllPerms = N => {\n const t0 = new Date();\n\n const res = d3.range(fact(N)).map(i => unrank(i, N));\n\n const t1 = new Date();\n const dt = t1 - t0;\n return { res, dt };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":129,"value":"buildAllPermsHeap = N => {\n // using Heap's method\n\n const t0 = new Date();\n\n const arr = d3.range(N);\n const res = [arr.slice()];\n const c = new Array(N).fill(0);\n let i = 1;\n\n while (i < N) {\n if (c[i] < i) {\n const k = i % 2 && c[i];\n const p = arr[i];\n arr[i] = arr[k];\n arr[k] = p;\n c[i] += 1;\n i = 1;\n res.push(arr.slice());\n } else {\n c[i] = 0;\n i += 1;\n }\n }\n\n const t1 = new Date();\n const dt = t1 - t0;\n return { res, dt };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":39,"value":"unrank = (r, n) => {\n if (!n) return 'missing permutation length';\n if (n < 2) return d3.range(n);\n if (n === 2) return r > 0 ? [1, 0] : [0, 1];\n\n const p = new Array(n).fill(0);\n let s, t, i;\n let nf = 1;\n\n d3.range(1, n).forEach(i => {\n p[i] = i;\n nf = nf * i;\n });\n\n d3.range(1, n)\n .reverse()\n .forEach(i => {\n s = (r / nf) | 0;\n r = r - s * nf;\n // swap\n [p[i], p[s]] = [p[s], p[i]];\n nf = nf / i;\n });\n return p;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"rank = permutation => {\n const n = permutation.length;\n\n if (n < 2) return 0;\n if (n === 2) return permutation[1];\n\n const p = Array(n);\n const pInv = Array(n);\n d3.range(n).forEach(i => {\n p[i] = permutation[i];\n pInv[p[i]] = i;\n });\n\n let r = 0;\n let s, t;\n d3.range(1, n)\n .reverse()\n .forEach(i => {\n s = p[i];\n // swap\n [p[i], p[pInv[i]]] = [p[pInv[i]], p[i]];\n [pInv[s], pInv[i]] = [pInv[i], pInv[s]];\n r = (r + s) * i;\n });\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"fact = n => {\n let f = 1;\n for (let i = 2; i <= n; i++) f *= i;\n return f;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"md`---\n## Annex\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":81,"value":"import { Range, Table } from '@observablehq/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"d3 = import('d3@6')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}