StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Rather than start with an algorithm, I've tried to think of a way to find a form for the maximum "swapping score", so that you know what to shoot for. Often an algorithm for producing the desired structure can emerge from such a proof. </p> <p>It's been a long time since university, but I've tried to think of a combinatorial model that will help to figure this out, without very much luck.</p> <p>I started by imagining the set of combinations as vertices in a graph, with a edges corresponding to the "adjacency" (only one element difference) of the combinations. So: </p> <ul> <li>"n choose k" vertices</li> <li>each vertex has degree k(n-k)</li> <li>number of edges = "n choose k" * k(n-k) / 2 = "n choose 2" * "n-2 choose k-1"</li> </ul> <p>There's a lot of symmetry to these graphs. The graph is the same for any given {n,k} as it is for {n,n-k}. If k=1 or k=n-1 it's the complete graph on n vertices (each combinations differs from all the others by only one character). I can't see an obvious algorithm from this, though.</p> <p>Edit: My next thought was to conceive the graph with a slightly different interpretation. You can think of each {n,k}-combination as a sequence of n bits where there are k 1s. The position of the 1s corresponds to which of the n characters is present in the combination. So for n=7 k=3, abc is 1110000, adg is 1001001, efg is 0000111. With this you can also imagine the points lying at the corners of an n-dimensional hypercube. So for a given subsequence, the edges match your "minimal swapping" criteria if they are co-planar: I think of them as "cutting planes" through the hypercube. </p> <p>You are looking for a Hamiltonian path through this graph of combinations, one that meets your special criteria.</p> <p>Another way to think of your problem is to minimize the number of times in the sequence that you <em>do</em> change which character in the combination is being altered.</p>

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