Many members of the club disliked the lack of variety and togetherness at the club. Although the club still had 12 members, some members were threatening to quit because each schedule was so short and there were so few people around each table.

To satisfy their request, the club decided to seat themselves around a big table and create a longer schedule. The twelve members of the club seated themselves in a schedule such that during each block of 55 days, no person was between the same pair of people. How was the schedule constructed?

(Based on The Round Table)

  There is a simple pattern which puts order into the madness of the arrays so far proposed, and from it a solution should easily be found (with the right tool –  like Penny I baulk at hand constructing the list). 

 I doubt that my Qbasic would be fast enough, and my C is a little rusty to attempt this, so I won’t try it.  However, here is my rationale and the basis of how I see such an algorithm developing.

 Take the digits 1, 2, 3 & 4.  Consider the 24 permutations listed from smallest to largest.  6 of these begin with 1 (which would be our first seat to fill).

 Of these 6 numbers, and examination of the first 3 will reveal triad groupings of digits (or their reverse) that in the latter 3 numbers, thus we can eliminate the latter 3.

We now have 3 combinations from the 4 elements that satisfy the rules.  As an alphabetical list this is: ABCD,  ABDC & ACBD.

 Now I do not propose to create an ordered permutation list of elements “ABC….KL” and then begin an elimination process.  Rather, I see the algorithm as creating the list ‘on the fly’.

 I have noted the occurrence of the triangular series in the second column in an earlier posting; these values will be useful in iterations within the algorithm.

 I propose four main string variables, “Initial.Seats”,  “AlphaSeats”,  “Triad.Forward” and “Triad.Backward”.   I will not need to allocate a storage array for all such groupings (doubt that the machine would even allow it); such an array would be list of “words” up to the point that they are created by the algorithm.

 Into “Initial.Seats” I place the elements “ABC….KL”.  I copy “Initial.Seats” into “AlphaSeats.”

I take a “List.Counter” which will count to 55 words. 

I initialise SeatWord[1] and copy A from “AlphaSeats”. 

With a new counter, “Triangle” which will not go beyond 10, I select B from “AlphaSeats” and concatenate it to SeatWord[1].

With a new counter “WordBuild” I begin to recurse through “AlphaSeat” looking to build my word.

Set at 1 I select C.  In “Triad.Forward” I place “ABC” and in “Triad.Backward” I place  “CBA”.  I then compare to see which is smaller.  I take this and compare it with SeatWord[1].

 As this grouping does not exist, I may concat C to SeatWord[1].  As I use an element from “AlphaSeats” I need to flag it, eg ‘*’.

If the group did exist, I initialise that letter and proceed to the next element in “AlphaSeats” that is not Flagged.

 Without detailing further, I think this illustrates my idea.  I don’t that there would need to be ‘wraparound’ test to check on the first and last two seats or the first two seats and the last, but it would be added insurance.

 In practice, with ABCDE,   I select A, B then I must have D, drop back to C and then add E.   For the next word I select A, B but now I only have E to choose, and then I drop back to C and finally add D.

 

 <o:p></o:p>

Posted by brianjn on 2004-07-29 21:22:41