{"_id":"k-choice-sort","_rev":"1-340c7d18063ef18df73315683f60989d","name":"k-choice-sort","dist-tags":{"latest":"1.0.9"},"versions":{"1.0.9":{"name":"k-choice-sort","version":"1.0.9","scripts":{"test":"tape ./tests/**/*.js | tap-bail | tap-colorize","build":"babel src --presets es2015 --out-dir dist"},"description":"K-Choice Sorter and Approximator","main":"dist/index.js","author":{"name":"Severin Ibarluzea","url":"seve@collegeai.com"},"devDependencies":{"babel-cli":"^6.26.0","babel-preset-es2015":"^6.24.1","left-pad":"^1.2.0","seamless-immutable":"^7.1.3","tap-bail":"^1.0.0","tap-colorize":"^1.2.0","tape":"^4.9.0"},"gitHead":"752060fa7af9184282291fcc7040226492bd2469","_id":"k-choice-sort@1.0.9","_npmVersion":"6.4.1","_nodeVersion":"10.11.0","_npmUser":{"name":"seveibar","email":"seveibar@gmail.com"},"dist":{"integrity":"sha512-gjie6urYoIE0ibWOwqP5qKiV8eKXtjReltAAfhQkEebe3GnrqP9htIK1gi4ZUzR3sIjUBiANMcpYdbjg5a8EbA==","shasum":"42bdc4ba14343839ec7d8f5d9f5ffa0b3f812b34","tarball":"https://registry.npmjs.org/k-choice-sort/-/k-choice-sort-1.0.9.tgz","fileCount":8,"unpackedSize":87967,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJcFgiQCRA9TVsSAnZWagAA82gP/j33i5S2NT1PmZdKh8dA\nVISHoUqfrRjVM2K1NozDZPucgNUcz9Fg/WTtnOJoGqq45ZK0rM/e/40yfabn\n7Os+HGDuvvE9Th/CJGw0eLQglpmJChphAL8S0vQdokHHHLKxslKimNinhJDp\nw5I2IG+njCFlT5q9iQofovIIezdNFqWc4WmO6aozEahs3ElRMRfKg2TVwjQa\nYAcXGn8fosASdYdZws34KZRWaim9J7VWpvsYTlnq12MS4M2gv1WpoOjw0LzS\nKut0plyZMZ3CWe6RVQy+5xc6HW+8hjVCMhoKMftJeVgxOvkSSqFmcBwomIGS\n1hWFiuP1NBniXS1JbKKTzCg8dg7U3UpqqB2OCGRc1MzVikJuGRjVkLHqANcG\nAdGyVXyldhbEDAIkYPEf9y/gm+QbWi0EyZ7mSQbTJgHX0Bav4nPBZBX+HJkA\nC4j79JF3MHEQ0aeoR5hIHPQlsvaL0s76ldtPIeEs/FLi1eUdCcAva1EiBH64\nYNTrWNQDetCZJa/Blq1K5ZzAXrjAw3gC3AB+nDCXJKCE6U39/iQk9ZY+g0HZ\nfMh6nqAr1V0vihsvfupfuROkPFSHgbItwdwwozftRPFHkvHlGX/Gq2IiCtlZ\nlMCiHGE9WpOmwsRO1iEGciw4JQExK/OwScEiympdh5DIHUbTjbGOoD62EGQG\nFWw+\r\n=3uV/\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQD1SUw6LmSjrZfoPmMaJNI4Ozqnf/InnUVnX8Vg0i5ZoQIhAPegNkGWGgn5/zVyGK5Kjogoex7NGrqlwdW2fkoeUJn3"}]},"maintainers":[{"name":"seveibar","email":"seveibar@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/k-choice-sort_1.0.9_1544947855935_0.9800386744576501"},"_hasShrinkwrap":false}},"time":{"created":"2018-12-16T08:10:55.934Z","1.0.9":"2018-12-16T08:10:56.106Z","modified":"2022-05-07T02:34:24.337Z"},"maintainers":[{"name":"seveibar","email":"seveibar@gmail.com"}],"description":"K-Choice Sorter and Approximator","author":{"name":"Severin Ibarluzea","url":"seve@collegeai.com"},"readme":"# K Choice Sorter (And Approximate Sorter)\n\nThis module solves the problem of approximately or completely sorting a list of\nitems by showing a user a set of 2 or more choices repeatedly.\n\n# Usage\n\n```javascript\nconst Sorter = require(\"@seveibar/k-choice-sort\")\n\n// Sort the items with binary choice (k=2)\nconst sorter = new Sorter({\n  items: [\"A\", \"B\", \"C\"],\n  maxCandidates: 2\n})\n\nconsole.log(\"Initial: \", sorter.getRankings())\nfor (let i = 0; !sorter.isSorted(); i++) {\n  const candidates = sorter.getCandidates()\n\n  // Show candidates to user, have user choose winning candidate\n  // For this example let's say alphabetical order wins\n  candidates.sort()\n  const winner = candidates[0]\n  const losers = candidates.slice(1)\n\n  sorter.recordAnswer(winner, losers)\n  console.log(`Iteration ${i + 1}:`, sorter.getRankings())\n}\n\n// Outputs:\n// Initial:     { A: 1   , B: 1   , C: 1   }\n// Iteration 1: { A: 1.5 , B: 0.5 , C: 1   }\n// Iteration 2: { A: 2   , B: 0.5 , C: 0.5 }\n// Iteration 3: { A: 2   , B: 1   , C: 0   }\n```\n\nCheck out `tests/basic.js` to see more methods and detailed output.\n\n# Motivation\n\nThis project began when designing some questions for the survey at [collegeai.com](https://collegeai.com).\n\nWhen you ask a student a question, like \"Do you like this college campus photo?\" The student is unable to properly preference it unless you say \"...relative to this photo?\". When you have many images of college campuses, this becomes a ranking problem. It's mentally straining for a student to order photos, so instead we ask a series of binary questions. Using these questions, we construct a ranking for each photo.\n\nFor an accurate ranking, a student would have to sort `n * log(n)` questions. This is generally impractical and time consuming for a student. Instead we ask a smaller number of questions and approximate the ranking of each photo. A simple way to think of this: we want to place each photo in bins such that we know the photos in each bin are next to each other in ranking. The order of the bins is known but not the order of the contents of each bin.\n\nEach student can be asked a binary comparison (k=2) OR a 4 answer question (k=4) (select your favorite of these 4 photos). How can a 4 answer question be used to reduce the total number of questions asked?\n\n# DAG Approach and Data Structure\n\nIn this approach, we construct a DAG where an edge points from any node (photo) with a lower absolute user preference to a node with an absolute higher user preference.\n\nEach time we ask a question, we may be able to infer new questions from prior edges.\n\nRepresenting this with a matrix, the algorithm is simple. Consider the following matrix **M**.\n\nEach column represents the relationship between A and B where A is the name of the column and B is the name of the row. There are 4 different relationships. 0 = unknown, 1 = (B > A), 2 = (B = A), -1 = (B < A). Note that the diagonal is always 2, and the cells with 1 are always reflected with cells containing -1.\n\nThe matrix begins in the following form.\n\n|         | A=1 | A=2 | A=3 | A=4 | A=5 |\n| ------- | --- | --- | --- | --- | --- |\n| **B=1** | 2   | 0   | 0   | 0   | 0   |\n| **B=2** | 0   | 2   | 0   | 0   | 0   |\n| **B=3** | 0   | 0   | 2   | 0   | 0   |\n| **B=4** | 0   | 0   | 0   | 2   | 0   |\n| **B=5** | 0   | 0   | 0   | 0   | 2   |\n\nHere's a correct example matrix after the algorithm is completed.\n\n|         | A=1 | A=2 | A=3 | A=4 | A=5 |\n| ------- | --- | --- | --- | --- | --- |\n| **B=1** | 2   | -1  | -1  | -1  | -1  |\n| **B=2** | 1   | 2   | -1  | -1  | -1  |\n| **B=3** | 1   | 1   | 2   | -1  | -1  |\n| **B=4** | 1   | 1   | 1   | 2   | -1  |\n| **B=5** | 1   | 1   | 1   | 1   | 2   |\n\nYou can solve with this matrix with a simple iteration.\n\n1.  M = initial matrix (shown above)\n2.  Find J unsolved candidates, where J is the number of photos that can be presented to the user. A simple way to do this is to find the column with the most unknowns, each unknown and the column index become candidates. Sorting the candidates by the highest number of unknowns (within a column index) yields significantly faster results. In general, the selected candidates should have the greatest expected potential for increasing the number of connections.\n3.  Ask question. Fill in ones where B=winner and A=$\\text{loser}\\_i$ where $1<i<J$, $i\\neq \\text{winner}$. Reflect to get -1s.\n4.  Iterate over each 0 in matrix at position $a,b$. If $M*{k,a}=1$ and $M*{b,k}=1$ for any $k=1...n$ then the cell $M*{a,b}=1$ else $M\\*{a,b}=0$. \\_This must be repeated until no operations are performed (there is a more performant solution but because n is often low, I haven't bothered to solve it)*\n5.  Reflect and fill in -1s.\n6.  Repeat 2-6 until matrix contains no unknowns (no 0s).\n\n# Getting Ranking From Matrix\n\nConvert each `-1` in `M` to `0` and each `2` to `0`.\nThe sum of each row will now correspond to the best approximation of the ranking.\n\nUsing the matrix above...\n\n|         | A=1 | A=2 | A=3 | A=4 | A=5 | Ranking |\n| ------- | --- | --- | --- | --- | --- | ------- |\n| **B=1** | 0   | 0   | 0   | 0   | 0   | 0       |\n| **B=2** | 1   | 0   | 0   | 0   | 0   | 1       |\n| **B=3** | 1   | 1   | 0   | 0   | 0   | 2       |\n| **B=4** | 1   | 1   | 1   | 0   | 0   | 3       |\n| **B=5** | 1   | 1   | 1   | 1   | 0   | 4       |\n\nThe algorithm correctly concludes that 1 < 2, 2 < 3, etc.\n\n# Approximate Sorting\n\nBounding the number of iterations is a sufficient approximation. One can also\nset the stop condition to be a maximum acceptable ranking group size, this gives\na strong error guarantee.\n","readmeFilename":"README.md"}