I was writing a routine for a game and stumbled upon some algorithm issues and a theoretical question about it. Here I'm mostly concerned with the latter, which may be phrased as a sort of graph counting problem. Phrased as "gift" or "voting" problem, it's related to some more textbook questions on the site, although my function-dependent parametrization seems more broad.
So say we got a set of $n$ players $ V = \{ v_1, v_2, \dots, v_n \} $ and they each announce their capacity $g(v_i)\in \{1, 2, \dots, n-1\}$ for the number of gifts they can give to other placers. Everybody shall receive as many gifts as they give. Our goal is to compute a task assignment, which can ultimately be expressed as a function $t\colon V \to {\mathcal P}(V)$ that the function $g$ passes through, namely an assignment that tells each player who they should give their gifts to. There's two conditions: $C_1$ says that they can't gift anybody twice, and in particular this implies $|t(v)|=g(v)$. And $C_2$ says that they can't gift themselves, which is to say $v\not \in t(v)$. While not a hard condition, I'd also like to maximize the number of mutual gifts, i.e. $C_3$ maximizes the number of player pairs $v, w$ such that $v\in t(w)\land w\in t(v)$.
In terms of directed graphs, we're given a vertex set together with the counts $g$ of their outgoing edges, and we're looking for a fitting graph, without edges that are parallel (in the same direction), nor have self-loops. I.e. a balanced simple digraph. And the number of opposing arrows should be maximal (or at least high). We can't always expect all to be back-and-forth, as e.g. shown by the necessary triangle $g=\{\langle v_1,1\rangle,\langle v_2,1\rangle,\langle v_3,1\rangle\}$. I'm not sure if 3 vertices doing their own thing is the minimum, but I expect it to.
Now I solve the problem with $C_1$ and $C_2$ quickly, by making use of random sampling: Using $g$ to turning $V$ into a list $M$ of size $\sum_{v\in V} g(v)$ (essentially a multi-set), we can shuffle $M$ and thus obtain an assignment $M\to M$. We do this so long as we got an assignment that fulfills all conditions. I.e.
def make_random_pairings(adjacency: dict) -> list:
multi_set = []
for v_src, v_targets in adjacency.items():
g_of_v: int = len(targets)
multi_set += g_of_v * [src]
multi_set_shuffled = list(multi_set)
random.shuffle(multi_set_shuffled)
return list(zip(multi_set, multi_set_shuffled))
def fulfills_condition(pairings) -> bool:
# Implementation of C_1, C_2 and to some extent C_3.
# For speedup of the filtering they can also be enforced already in 'make_random_pairings'
def run_main():
adjacency = {v: v.giving_capacity * ["unknown yet"] for v in V_USERS}
pairings = make_random_pairings(adjacency)
while not fulfills_condition(pairings): # Might need many trials
pairings = make_random_pairings(adjacency)
for v_src, v_targets in to_adjancency(pairings).items():
print(f"{v_src.name}, please give to:")
for v in v_targets:
print(f" {v.name}")
(I have a script to compute a solution in this manner and even a function to draw the graph. The above shows the main logic of it - I can post if it anybody wants it in full. That said, I found it surprisingly difficult write down an algorithm that does this deterministically, and is not explicitly "anti - $C_3$". The issue is that if I naively fix an order in which assignments are determined, one after the other, there was always some $g$ such that my routine was forced into self-gifting or multiple-gifting. I think this especially happens if a few players have very high gifting capacity. Random sampling $g$'s for testing the deterministic ideas quickly runs into issues. So a side question is whether this is a known algorithmic task, what the solution is, or - if it's not standard - if you have an idea how to do this, preferably while imposing $C_3$ to the optimum.)
As running this routine is not too time critical, I found this works fine for small $|V|$, at least when not imposing $C_3$. Now I got a variant of the routine for which I set a minimum percentage mutual gifts, and gives me the task when that condition is fulfilled too. I found demanding 90% of mutual gifts still runs in a sensible time - but clearly for this condition the sampling approach is not optimal.
Now if $g(v)=1$ for all $v$, then $C_1$ is trivially fulfilled and $C_2$ exactly says that we're looking for a derangement (Wikipedia). The number of derangements ($!n$) over general permutations is $\frac{!n}{n!}=\sum_{k=0}^n\tfrac{1}{k!}(-1)^n$. In the limit of large $n$, this converges to ${\mathrm e}^{-1}$.
My question arose when wondering how quickly I can expect the sampling-algorithm to give a result, while imposing the harder conditions: Given $g$, what's the ratio of graphs fulfilling the conditions ($C_1$ plus $C_2$, but more generally one may ask about $C_1$ or $C_2$ independently, and this can be extended by $C_2$. But that's all bonus and the post shall be concerned with $C_1$ plus $C_2$, say.) It would seem that there should be an algebraic formula dependent on $n$ and $g$, which when imposing $g(v)=1$ reduces to the derangement formula. If it's too hard to state, maybe the limit $n\to\infty$ value is interesting: Under which conditions on $g$ is the value, in the limit, actually not dependent on $g$ anymore. I have the feel that it will be broader than demanding $g(v)=1$. Imposting $C_3$ (incrementally with a percentage of mutual gifts), empirically, seems to push down the changes of randomly picking a valid assignment significantly.