Q: How can I set up a random gift exchange that’s different from year to year?

The original question was: I’ve got a large family and we do a yearly gift exchange one person to one person. And I’d like to make a algorithm or something to do random selection without repeating for some time. And to be able to take old data and put it in to avoid repeats. I’m pretty good at math I’m 29 and my trade is being a machinist so I’ve got some understanding of how things kinda work.

Physicist: A good method should be trivially easy to keep track of from year to year, work quickly and simply, never assign anyone to themselves, make sure that everyone gives to everyone else exactly once, and be unobtrusive enough that it doesn’t bother anybody.  Luckily, there are a few options.  Here’s one of the simplest.

Give each of the N people involved a number from 1 to N.  The only things you’ll need to keep track of from year to year are everyone’s number and an index number, k.  Regardless of who the best gift-giver is, there are no best numbers and no way to game the system, and since no one wants to keep track of a list from one year to the next, you should choose something simple like alphabetical numbering (Aaron Aardvark would be #1 and Zylah von Zyzzyx would be #N).

Draw N dots in a circle then, starting with dot #1, draw an arrow to dot #(1+k), and repeat.  There’s nothing special about any particular dot; since they’re arranged in a circle #1 has just as much a claim to be first as #3 or #N.  When you finally get back to dot #1, you’ll have drawn a star.  Each different value of k, from 1 to N-1, will produce a different star and a different gift-giving pattern.  For example, if N=8 and k=3, then you get a star that describes the pattern {1→4→7→2→5→8→3→6→1} (that is “1 gives to 4 who gives to 7 …”).

When N is prime, or more generally when N and k have no common factors, you’ll hit every dot with a single star.  Otherwise, you have to draw a few different stars (specifically, “the greatest common divisor of k and N” different stars).  For example, if N=8 and k=2, then you need two stars: {1→3→5→7→1} and {2→4→6→8→2}.

Given N points, you can create a star by counting k points and drawing a connection.  This works great if N is a prime (bottom), since you’ll always hit every point, but when N isn’t prime you’ll often need to create several stars (top).

That’s why drawing is a good way of doing this math: it’s easy to see when your star is weird-shaped (your k changed halfway through) and really easy to see when you’ve missed some of the dots.

The “star method” gives you N-1 years of “cyclic permutations” (“cyclic” because when you get to the end you just go back to the beginning).  However, for large values of N that’s only a drop in the permutation sea.  Were you so determined, you could cyclicly permute N things in (N-1)! ways.

However!  With a family of 6 you’d need 5! = 1x2x3x4x5 = 120 years to get through every permutation.  More than time enough for any family to gain or lose members, or for some helpful soul to start questioning the point.  Moreover!  Each of those permutations are similar enough to others that you’ll start to feel as though you’re doing a lot of repeating.  For example: {1→2→3→4→5→6→1}, {1→2→3→4→6→5→1}, {1→2→3→5→6→4→1}, …

For those obsessive, immortal gift-givers who want to hit every permutation with the least year-to-year change, just to fight off boredom for another thousand years, there’s Heap’s algorithm.  For the rest of us, drawing stars is more than good enough.