Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Background:

So the school I work at has a policy that we try and sit the kids next to as many different other kids as possible throughout the academic year. This means rejigging the seating plan as often as you can be bothered to.

With a decentish understanding of VBA, I figured I'd write a macro to take care of this for me, but I've come up against a snag.

The basic algorithm is to shuffle the list, then transcribe that to a seating plan in a predefined way. The hope is to shuffle the list in such a way that no two students are adjacent that were before.

But my problem is there seems no simple way of characterising these shuffles.

Maths

So suppose we have an ordered list of n elements (possibly it will be easier to consider it as cyclic list, so that n is adjacent to 1), how can one reliably generate the maximum number of reorderings of that list in which no two reorderings share adjacent pairs?

One obvious strategy might be a random walk on $S_n$, but without knowing the maximal number this could go on forever looking for a reordering that wasn't there. So a natural supplementary question is: what is the maximal number of such reorderings?

Failing that, what is a reliable way of making (a possibly suboptimal number of) 'mixing' reorderings?

So far I have experimented with Faro shuffles (which do not guarantee mixing under composition), groups of invertible elements in $\mathbb{Z}_n^\times$ (multiplicative group of integers modulo n- which seem quite meagre in only offering $ \phi(n)$/2 reorderings), and have toyed with some random-walk code, all to no avail.

I'm sure this is all just a reflection of my ignorance of combinatorics- that the answer will turn out to be a fraction with a couple of factorials, or that it's a famous problem or some such. But I'm stumped.

Any help you could give would be ace. Thanks!

share|improve this question

2 Answers 2

up vote 3 down vote accepted
+250

For a cyclic list what you're effectively asking for is a Hamilton Decomposition of the complete graph (each Hamiltonian cycle corresponds to a single day's seating, and the "no two sitting together twice" condition is equivalent to no edge appearing in two cycles). A maximal construction for these was found by Walecki in the 19th century, though I'm having trouble finding a good accessible reference for the actual construction.

Section $3$ of this paper of David Pike gives the construction for $n$ odd, which is perhaps easier visualized through the drawing on page 118 of Brett Stevens' "Anti-Oberwolfach Solution" paper (link is to a Google Books preview -- hopefully the page in question is visible). Alspach, Bermond, and Sotteau's paper "Decomposition into Cycles I: Hamiltonian Decompositions" describes the general construction (ditto on the Google Books preview).

The construction for $n=2k+1$ odd seems to work roughly as follows. Given a person $a$ between $1$ and $n$, define a "zig-zag starting at $a$" to be the sequence $$a,a+1,a-1,a+2,a-2,\dots,a+(k-1),a-(k-1),a+k$$ where all operations are taken modulo $2k$. Such a zig-zag contains every number between $1$ and $2k$, and we can form a Hamiltonian cycle by connecting $2k+1$ to both ends. Doing this to each zig-zag from $a=1$ to $a=k$ gives Walecki's decomposition.

share|improve this answer
    
I know the comment box is asking me to "avoid saying "thanks"", but I just wanted to say this was exactly what I was looking for. A beautiful little piece of mathematics that does the job flawlessly. 250 rep well-earned! Thanks! –  Tom Boardman Oct 8 '13 at 17:33

I assume that your school doesn't have King Arthur's Round Table, so they aren't really in one long chain.
Are they just in pairs? If you have $N$ tables, each sits 2 students, you can do this:
(1) Student 1 sits in the left-hand side of Table 1 forever.
Each time you move students,
(a) everyone on the left-hand side moves up one table,
(b) everyone on the right-hand side moves down one table
(c) The left-hand student on Table $N$ moves to the right-hand side of Table $N$
(d) The right-hand student on Table 1 moves to the left-hand side of Table 2.
You can disguise it obviously by going to the $m^{th}$ position instead of the next position. It has the disadvantage that the people in front and behind you stay the same.
If you put the tables in some order (not Table $k$ in front of Table $k+1$, you might be able to make the people in front and behind you change regularly. I am not sure how to do that. If $N+1$ is prime, you might find a generator $g$ of $\mathbb{Z}_{N+1}^{\times}$ and order the tables according to the powers of $g$.
That just leaves the people in the next aisle; I think that depends on how many aisles.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.