OK, here's one I haven't had the chance to solve yet (the problem is my original)
On christmas, our office has a secret santa event. Everyone's name is put into a bowl. Each employee comes in random order, and picks a name from the bowl (there is the unfortunate possibility of one picking their own name).
Looking at the (employee name - A, name of employee on card - B), there must be at least one loop (starting with a random employee, then going to the next employee based on the card the previous one chose).
A loop configuration is a list of the size of loops in ascending order.
An employee configuration is a list of numbers, giving each employee the number of the other employee on the car he chose.
For n employees, there are n! employee configurations.
Return, given n, the number of employee configurations for each loop configuration.
Example: n=1
{Loop Configurations, Corresponding employee configurations} = {(1), 1} -- there is only one loop possible, the employee to himself. There is only one employee configuration to begin with.
Example: n=2
{Loop, Configs} = {(2), 1}
{Loop, Configs} = {(1, 1), 1}
Either a loop of two employees, each being the santa of the other, or two loops, each employee being the santa of himself.
The sum of configs sums to 2! which is 2.
Example: n=3
{(3), 2}
{(2, 1), 3}
{(1, 1, 1), 1}
There are 3! employee configs in total. Each one being the santa of himself amounts to a single config. A loop going through all the employees has two possibilities (one in each direction (1, 2, 0) or (2, 0, 1) ). The rest of configurations belong to the middle case. Those configs are detailed below:
(0, 2, 1)
(2, 1, 0)
(1, 0, 2)
I haven't come down to an implementation yet, but the problem itself needs some understanding. I am working on my writing-a-problem skills, so please let me know where it needs clarification.