StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><a href="http://portal.acm.org/citation.cfm?id=1036677&dl=&coll=" rel="noreferrer">Art of Computer Programming Volume 4: Fascicle 3</a> has a ton of these that might fit your particular situation better than how I describe.</p> <h2>Gray Codes</h2> <p>An issue that you will come across is of course memory and pretty quickly, you'll have problems by 20 elements in your set -- <sup>20</sup>C<sub>3</sub> = 1140. And if you want to iterate over the set it's best to use a modified gray code algorithm so you aren't holding all of them in memory. These generate the next combination from the previous and avoid repetitions. There are many of these for different uses. Do we want to maximize the differences between successive combinations? minimize? et cetera.</p> <p>Some of the original papers describing gray codes: </p> <ol> <li><a href="http://portal.acm.org/citation.cfm?id=2422.322413" rel="noreferrer">Some Hamilton Paths and a Minimal Change Algorithm</a></li> <li><a href="http://portal.acm.org/citation.cfm?id=49203&jmp=indexterms&coll=GUIDE&dl=GUIDE&CFID=81503149&CFTOKEN=96444237" rel="noreferrer">Adjacent Interchange Combination Generation Algorithm</a></li> </ol> <p>Here are some other papers covering the topic:</p> <ol> <li><a href="http://www.cs.uvic.ca/~ruskey/Publications/EHR/HoughRuskey.pdf" rel="noreferrer">An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm</a> (PDF, with code in Pascal)</li> <li><a href="http://portal.acm.org/citation.cfm?doid=355826.355830" rel="noreferrer">Combination Generators</a></li> <li><a href="http://www4.ncsu.edu/~savage/AVAILABLE_FOR_MAILING/survey.ps" rel="noreferrer">Survey of Combinatorial Gray Codes</a> (PostScript)</li> <li><a href="http://www.springerlink.com/content/7lvmm575n85xv5v0/" rel="noreferrer">An Algorithm for Gray Codes</a></li> </ol> <h2>Chase's Twiddle (algorithm)</h2> <p>Phillip J Chase, `<a href="http://portal.acm.org/citation.cfm?id=362502" rel="noreferrer">Algorithm 382: Combinations of M out of N Objects</a>' (1970)</p> <p><a href="http://www.netlib.no/netlib/toms/382" rel="noreferrer">The algorithm in C</a>...</p> <h2>Index of Combinations in Lexicographical Order (Buckles Algorithm 515)</h2> <p>You can also reference a combination by its index (in lexicographical order). Realising that the index should be some amount of change from right to left based on the index we can construct something that should recover a combination.</p> <p>So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change, and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change, but accounts for more change since it's in the second place (proportional to the number of elements in the original set).</p> <p>The method I've described is a deconstruction, as it seems, from set to the index, we need to do the reverse --which is much trickier. This is how <a href="http://portal.acm.org/citation.cfm?id=355739" rel="noreferrer">Buckles</a> solves the problem. I wrote some <a href="https://stackoverflow.com/questions/561/using-combinations-of-sets-as-test-data#794">C to compute them</a>, with minor changes --I used the index of the sets rather than a number range to represent the set, so we are always working from 0...n. Note:</p> <ol> <li>Since combinations are unordered, {1,3,2} = {1,2,3} --we order them to be lexicographical.</li> <li>This method has an implicit 0 to start the set for the first difference.</li> </ol> <h2>Index of Combinations in Lexicographical Order (McCaffrey)</h2> <p>There is <a href="http://msdn.microsoft.com/en-us/library/aa289166.aspx" rel="noreferrer">another way</a>:, its concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it also does not produce duplicate combinations:</p> <p>The set <a href="https://i.stack.imgur.com/Txetz.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/Txetz.gif" alt="x_k...x_1 in N"></a> that maximizes <a href="https://i.stack.imgur.com/HOj5o.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/HOj5o.gif" alt="i = C(x_1,k) + C(x_2,k-1) + ... + C(x_k,1)"></a>, where <a href="https://i.stack.imgur.com/vIeiI.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/vIeiI.gif" alt="C(n,r) = {n choose r}"></a>.</p> <p>For an example: <code>27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)</code>. So, the 27th lexicographical combination of four things is: {1,2,5,6}, those are the indexes of whatever set you want to look at. Example below (OCaml), requires <code>choose</code> function, left to reader:</p> <pre class="lang-fs prettyprint-override"><code>(* this will find the [x] combination of a [set] list when taking [k] elements *) let combination_maccaffery set k x = (* maximize function -- maximize a that is aCb *) (* return largest c where c < i and choose(c,i) <= z *) let rec maximize a b x = if (choose a b ) <= x then a else maximize (a-1) b x in let rec iterate n x i = match i with | 0 -> [] | i -> let max = maximize n i x in max :: iterate n (x - (choose max i)) (i-1) in if x < 0 then failwith "errors" else let idxs = iterate (List.length set) x k in List.map (List.nth set) (List.sort (-) idxs) </code></pre>

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