30:[{"id":"4e3b12b3907ed11c7df8eb0e70464627b5b7cb9165d3932248fe1bc48a778265ce6c050b551f6018f787e969714b0effb46ee9b88e1b9ce6742c7632d1f568be","href":"https://static.observableusercontent.com/files/4e3b12b3907ed11c7df8eb0e70464627b5b7cb9165d3932248fe1bc48a778265ce6c050b551f6018f787e969714b0effb46ee9b88e1b9ce6742c7632d1f568be","name":"numbered-balls.jpeg","type":"image/jpeg","lastModified":1618173570500.471,"size":209902}] 2e:{"title":"Ranking Subsets","cells":[{"id":0,"value":"md`# Ranking Subsets\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":911,"value":"md`

${tex`\\binom{n}{k}`} ways to choose ${tex`k`} from ${tex`n`} balls - But how to rank these subsets ? 🤔

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":919,"value":"md`Ref. [Kreher and Stinson Combinatorial Routines](https://people.math.sc.edu/Burkardt/f_src/combo/combo.html)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":599,"value":"viewof n = Range([3, 20], { step: 1, value: 9, label: 'Nb Items' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":605,"value":"viewof k = Range([1, n], { step: 1, value: (n / 2) | 0, label: 'Subset size' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":650,"value":"md`## Lexicographic Order\n\n**Lex** order is that of a dictionary. \nHere the alphabet is ${tex`\\left \\{0, 1, 2,...,n\\right \\}`}.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":630,"value":"{\n const arr = allLexSubsets.arr;\n return Table(arr, {\n align: { rank: 'left' },\n width: { rank: ' 10%', subset: '90%' }\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":635,"value":"md`*Lexicographic order: Rank-Subset(${n},${k}) map \nrank = 0...${allLexSubsets.arr.length.toLocaleString()}*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":611,"value":"allLexSubsets = {\n const arr = [];\n\n let _T = null;\n d3.range(Cnk(n, k)).forEach(r => {\n const T = unrankLex(r, k, n);\n\n const r2 = rankLex(T, n);\n const testR = r === r2;\n\n const T2 = r > 0 ? nextLex(_T, n) : null;\n const testN = JSON.stringify(T) === JSON.stringify(T2);\n\n arr.push({ rank: r, subset: T, testR, testN });\n _T = T.slice();\n });\n const testR = arr.map(e => e.testR).every(e => e);\n const testN = arr\n .slice(1)\n .map(e => e.testN)\n .every(e => e);\n\n return { arr, testR, testN };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":641,"value":"md`### Tests:\n+ Is \\`unrankLex()\\` the inverse of \\`rankLex()\\` for all subsets ? ${allLexSubsets.testR}\n+ Is \\`nextLex()\\` consistent with \\`rank/unrankLex()\\` ? ${allLexSubsets.testN}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":660,"value":"md`## Colexicographic Order\n\n**Colex** order is obtained by:\n+ reflecting all tuples\n+ applying Lex order\n+ reflecting the tuples again\n\nHere the alphabet ${tex`\\left \\{0, 1, 2,...,n\\right \\}`}.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":665,"value":"{\n const arr = allCoLexSubsets.arr;\n return Table(arr, {\n align: { rank: 'left' },\n width: { rank: ' 10%', subset: '90%' }\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":667,"value":"// md`*Colexicographic order: Rank-Subset(${n},${k}) map*`\n\nmd`*Colexicographic order: Rank-Subset(${n},${k}) map \nrank = 0...${allCoLexSubsets.arr.length.toLocaleString()}*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":663,"value":"allCoLexSubsets = {\n const arr = [];\n\n let _T = null;\n d3.range(Cnk(n, k)).forEach(r => {\n const T = unrankCoLex(r, k, n);\n\n const r2 = rankCoLex(T, n);\n const testR = r === r2;\n\n const T2 = r > 0 ? nextCoLex(_T, n) : null;\n const testN = JSON.stringify(T) === JSON.stringify(T2);\n\n arr.push({ rank: r, subset: T, testR, testN });\n _T = T.slice();\n });\n const testR = arr.map(e => e.testR).every(e => e);\n const testN = arr\n .slice(1)\n .map(e => e.testN)\n .every(e => e);\n\n return { arr, testR, testN };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":672,"value":"md`### Tests:\n+ Is \\`unrankCoLex()\\` the inverse of \\`rankCoLex()\\` for all subsets ? ${allCoLexSubsets.testR}\n+ Is \\`nextCoLex()\\` consistent with \\`rank/unrankCoLex()\\` ? ${allCoLexSubsets.testN}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":704,"value":"md`## Performace Tests\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":895,"value":"viewof n_test = Range([3, 25], { step: 1, value: 20, label: 'Nb Items' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":897,"value":"viewof k_test = Range([1, n], {\n step: 1,\n value: (n_test / 2) | 0,\n label: 'Subset size'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":836,"value":"viewof btnRunTest = html`