How do I generate combinations where each successive combination is least like the previous? I have a pool of 9 people, from which I want to weekly choose 5 to take to lunch.  When I generate combinations in Excel, I get something like the following:
First few combinations
The problem is, if I proceed down the list, the first 4 people are chosen every time, with each iteration only changing the 5th person.  I would like to make each iteration as different from the previous one as possible to maximize the variety. In practice, it could mean that the second iteration shares only one name with first.  Any ideas how to change the generation method to maximize variety from week to week?  Thanks!
 A: I have no proof that this is optimal, but I'd try numbering the combinations with indexes from 1 to 126, and creating an additional column which has value ABS(index - 63) and then sorting the rows according to that additional column, with a stable sort.
The sort will interleave the combinations from the two ends inwards, so most of the time two adjacent combinations will be mainly different (except at the very middle of the list).
Another possibility for the sort key column is MOD(index - 1, 63). That rearranges the combinations as if they were a deck of cards split exactly in half and then exactly riffle shuffled.
Another possibility is just to generate random values for the column you use as the sort key (as suggested by Dubs while I was writing this); this will remove the deterministic similarity you have between successive results of Excel's combination algorithm, but whether two successive combinations of the sorted output are similar will then be a matter of luck.
The best way to solve your problem that I can think of is to formalize what you mean by "different" into a distance function over pairs of combinations which is smaller the more different the pair is, and then use this distance function to create a Traveling Salesman Problem. The solution, however, would probably be much more expensive in computing time than you would probably want to invest, here.
A: Consider the graph whose vertices are all $\binom{9}4$ subsets of friends of size four, and with an edge between subsets if they are disjoint. You want a Hamiltonian cycle in this graph; each vertex represents the friends not present at your lunch. 
This graph is known as the Knesser graph $K({9,4})$. According to this preprint on the arXiv, $K(9,4)$ does have a Hamiltonian cycle. 
