Dinner Club solution
Here is a seating schedule for the 25-member dinner club problem as posed by Alex last week. The solution was generated with a doubly-recursive graph walking algorithm.
The inner recursion function was a fairly simple algorithm for constructing a single night's schedule. The members are arranged in a circular list. Member 'A' is placed on the nightly dinner schedule, then starting from 'A' goes clockwise around the list, looking for the first member that meets the following criteria:
a) has not dined with the last member on the schedule.
b) has not already been selected for tonight's dinner.
The member is then added to the night's schedulw and the funtion is applied recursively to that member. The function terminates successfully when all members have been selected for tonight's dinner and the last member selected has not already dined with 'A'. The function fails if it cannot find a member eligible for selection. If it fails at any level, it backs up one level, looks for the next available member and recurses again.
This function was invoked from a loop to generate nightly schedules for (n-1)/2 nights.
In terms of performance, it worked better than expected - when it worked. In fact, for groups of size 3, 5, 7, 11 and 13, it delivered the theoretical best-case performance by producing each night's schedule in a single pass with no backtracking.
Although it found a solution for most cases tested, it failed outright on a few, including the 25 member case in Alex's original question. The failure was due to the fact that some sequences of seating schedules could result in fragmentation of the graph, preventing complete (all members seated) schedules from being generated for subsequent nights. Nevertheless, it proved to be a very good heuristic, so I retained it as the core of the general solution.
To resolve these failure cases, I replaced the outer nightly iteration loop with another recursive search. If the inner algorithm fails to generate a schedule for any night, the outer algorithm backs up one night and instructs the inner algorithm to pick the next available seating arrangement for that night. It then attempts to continue for the remaining nights.
If anyone is interested, you are welcome to the code.
The 25 night seating schedule was computed with 5742 iterations of the inner function. They are output in reverse order due to the recursion:
Night 12: A L U H T G O B M Y K W J V D P C N X I R F Q E S
Night 10: A K T F O X H R D N Y J S C M W I U G Q B L V E P
Night 9: A J R C L T D M U F N W E O V B K X G P Y I S H Q
Night 8: A I Q Y G N T C K S D L R B J U E M V H P X F W O
Night 7: A H O U C J Q X D K R Y F M T E L S B I P W G V N
Night 6: A G M S Y E K Q W C I O T B H N U D J P V F L X R
Night 5: A F K P U B G L Q V C H M R W D I N S X E J O Y T
Night 4: A E I M Q U Y D H L P T X C G K O S W B F J N R V
Night 3: A D G J M P S V Y C F I L O R U X B E H K N Q T W
Night 2: A C E G I K M O Q S U W Y B D F H J L N P R T V X
Night 1: A B C D E F G H I J K L M N O P Q R S T U V W X Y
