cristoper / sinterbot Goto Github PK

I should check to make sure sinterbot installs/runs on Windows.

Originally I thought people might want to maintain several santa lists with a single smtp.conf. However, it is a bit complicated and confusing. Better to just include smtp conf in the same config file as santas.

• Allow sending to non STARTTLS servers?
• Allow specifying subject/body templates?

Colors, maybe?

The weblog post is incomplete and doesn't talk about counting permutations with more constraints. I need to get a better handle on counting and generating functions and attempt to answer them! I ran out of time this year.

Some draft that got cut from the article:

=== More constraints

Mere derangements are fine, but what if our friends think secret santa is more fun if two people cannot be assigned to each other (that there should be no fixed points or two-cycles)? or that there should be only one cycle?

There can of course be more elaborate constraints and questions, the sorts of things investigated by https://en.wikipedia.org/wiki/Random_permutation_statistics[statistics of random permutations] and https://en.wikipedia.org/wiki/Generating_function[generating functions].

==== Single n-cycle

The easiest case is if we want to restrict assignments to a single cycle that includes all latexmath:[n] elements. A permutation with one cycle is a derangement by definition.
Choose any person in the set. There are latexmath:[n-1] remaining people to choose from to assign as their secret santa. After making that assignment there are latexmath:[n-2] remaining people to assign as the previous choice's santa. Carried out to the end we see that there are

[latexmath]
++++
\begin{align*}
&(n-1)(n-2)\cdots (n-(n-1))\
&= (n-1)!
\end{align*}
++++

possible n-cycle permutations of latexmath:[n] elements. (For five people that means there are latexmath:[4! = 24] possible single cycle secret santa assignments).

==== Counting k-cycles

• probability of a permutation containing a 2-cycle
• probability of derangement containing a k-cycle
• • black lists

low level: https://github.com/signalapp/libsignal
easier: https://github.com/AsamK/signal-cli

It is currently possible to specify blacklists that prevent a valid assignment from being found so sinterbot derange never returns.

If nothing else it should time out with a suggestion to check blacklists.

Currently the weblog post mentions that Martínez et al's algorithm works because of a "specific probability" but it doesn't explain how that is derived from the recurrence relation for Dn.

On the weblog post I talk about counting derangements with k-cycles, but what about the number of derangements given the blacklists?