StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>for a database that has X companies, create an X by X grid, and populate each cell with a company name. Any given company name should appear exactly once in each row and column. For example, for a database of ten companies, each with a one character name, one such grid would look like this:</p> <pre><code>ABCDEFGHIJ BCDEFGHIJA CDEFGHIJAB DEFGHIJABC EFGHIJABCD FGHIJABCDE GHIJABCDEF HIJABCDEFG IJABCDEFGH JABCDEFGHI </code></pre> <p>The company in the xth row and yth column will appear x units from the top of the list on the yth day. In other words, each day you refer to a different row for the ordering of your company names. This scheme satisfies two of your criteria: that each element must be in the #1 slot at least once every X days, and that any particular element should not stagnate in the same position for a long time. But there is still the problem that company B always appears below company A, so some additional work is needed.</p> <p>Choose two columns at random and swap them around. Repeat this process until the columns are sufficiently randomized (See <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="nofollow">Fisher-Yates Shuffle</a> for a linear-time way to do this). One such result might look like this:</p> <pre><code>HIDEJBGCAF IJEFACHDBG JAFGBDIECH ABGHCEJFDI BCHIDFAGEJ CDIJEGBHFA DEJAFHCIGB EFABGIDJHC FGBCHJEAID GHCDIAFBJE </code></pre> <p>Now, on average A will be in front of B 50% of the time. The actual percentage will vary, but it will fall on a bell curve centered around 50%, and only rarely will it reach a very uneven proportion.</p> <p>Company B might complain that it always appears in the #1 slot exactly one day after company A appears at #1. If this is a problem, then perform a shuffle on rows too:</p> <pre><code>GCDHBIFEAJ HDEICJGFBA BHICGDAJFE JFGAEBIHDC IEFJDAHGCB AGHBFCJIED CIJDHEBAGF EABFJGDCIH FBCGAHEDJI DJAEIFCBHG </code></pre> <p>Now you have an ordering scheme with the following properties:</p> <p>Pros</p> <ul> <li>over the course of an X-day-long cycle, all X companies appear in the #1 slot.</li> <li>over the course of an X-day-long cycle, no company will ever stagnate in the same slot. Once it occupies slot K, it will not return to that slot for the rest of the cycle. (In the worst case, it still might "hover" around the same area for a while, but eventually it will go everywhere on the list)</li> <li>no one company will appear over another much more than 50% of the time. The more companies you have, the closer to 50% it approaches.</li> <li>which company will appear in the #1 slot is unpredictable, so no one can legitimately claim a bias based on when a company is spotlighted.</li> </ul> <p>Cons</p> <ul> <li>for a database of N companies, generating a grid takes O(N^2) time and memory. You only need to generate one every N days, and you can do it ahead of time, so you can amortize the cost down to O(N) time.</li> <li>Companies do not "bubble up" over time. I believe this constraint conflicts with the "no company should appear above another too much" constraint; if all companies bubble upwards with approximately equal velocity, then the ones that started higher will usually be above the ones that started lower. The method I've given is the result of discarding one requirement in order to satisfy another mutually exclusive requirement.</li> <li>for any X-day-long time period, there is a 1/N chance that a company will appear in the #1 slot two days in a row. This occurs, for example, when company A is in the #1 slot on the last day of the cycle, and when you generate a new grid, company A is in the #1 slot on the first day of the cycle. If this is undesirable, you can perform another shuffle until A isn't in the first slot.</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload