Copious Secret Santa / Voting assignment

copious_secret_santa.py

"""
Script used in the video
https://youtu.be/2b9fOpX0zKY

Formal structure: balanced simple digraph
(Important special properties out-degrees equals the in-degrees, no self-loops, no parallel arrows)

1. Proof task: Count them, given any assginment of out-degrees.
How does it compare to just random disgraphs with that those out-degrees?
1. Coding task: Generate one given the out-degrees, fast. (I have a bad, probabilistic solution)

I think that problem could be google-able for the case where all vertices share the degree.
Starters:
There are n! digraphs with all out-degrees 1 and n!/p(n) without self-loops (derangements),
where p(n) is some simple rec. sequence.
There are 2^(n^2) digraphs and 2^(n^2)/2^n without self-loops.

2. Count graphs when further assuming there are k degree l cycles.
In particular, k two-cycles (i.e. back and forther arrows).
2. Coding task: Maximize the two-cycles

https://en.wikipedia.org/wiki/Directed_graph
https://en.wikipedia.org/wiki/Derangement
"""

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt


# Config
DEGREES = dict(
    Hiro=1,
    Stut=1,
    Dave=2,
    Vesa=10,
    Oreph=2,
    Tommy=2,
    MrTax=1,
    Panig=4,
    Hubba=5,
    Ulysseus=2,
    Fandango=3,
)
#DEGREES = {name : 1 for name in DEGREES.keys()}  # tmp
NAMES = list(DEGREES.keys())
NUM_NAMES = len(NAMES)
NUM_EDGES = sum(DEGREES.values())
REC_EDGE_TARGET = NUM_EDGES * (40 / 100)
print(f"NUM_NAMES = {NUM_NAMES}, REC_EDGE_TARGET target = {int(REC_EDGE_TARGET)}")

USER_DERANGEMENTS_PERC = sum([(-1)**k / np.math.factorial(k) for k in range(NUM_NAMES + 1)])
print(f"USER_DERANGEMENTS = {int(np.math.factorial(NUM_NAMES) * USER_DERANGEMENTS_PERC)}, ({round(100 * USER_DERANGEMENTS_PERC)} %)")

def draw_graph(edges) -> None:
    G = nx.DiGraph(directed=True)

    # Position all labels
    G.add_edges_from(edges)
    pos = nx.shell_layout(G)

    # Add non-reciprocal edges
    not_rec = []
    for e in edges:
        if e[::-1] not in edges:
            not_rec.append(e)
    nx.draw_networkx_edges(G, pos, edgelist=not_rec, edge_color="black", arrows=True, arrowsize=15, connectionstyle="arc3,rad=0.0",)

    # Add reciprocal edges
    rec = []
    for e in edges:
        rev_e = e[::-1]
        if e not in not_rec and rev_e not in (rec + not_rec):
            rec.append(e)
    nx.draw_networkx_edges(G, pos, edgelist=rec, edge_color="g", arrows=False, arrowsize=5, connectionstyle="arc3,rad=0.0",)

    # Draw
    nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap("jet"), node_size=0)
    nx.draw_networkx_labels(G, pos, font_size=10)
    plt.axis("off")
    plt.show()


def log(edges: list):
    print(f"\nTotal number of votes: {NUM_EDGES}\n")
    adjacency = {src: [] for src, _target in edges}
    for src, target in edges:
        adjacency[src].append(target)
    for src, targets in adjacency.items():
        print(src + " => " + ", ".join(targets) + f" ({len(targets)} gifts)")


def num_reciprocal_edges(edges: list) -> int:
    # Number of pairs (s, t) such that (t, s) is also in 'edges'
    return sum(pair[::-1] in edges for pair in edges)


def run_main():
    perc = 0  # For print
    rec_check = 0  # For print

    edges = []
    while num_reciprocal_edges(edges) < REC_EDGE_TARGET:
        targets = []
        while len(targets) < NUM_EDGES:

            sources = []
            for name, degree in DEGREES.items():
                sources += [name] * degree  # Make ordered multiset of DEGREES
            np.random.shuffle(sources)

            #targets = list(sources); random.shuffle(targets)

            targets = []
            names_todo = list(sources)
            excluded = {name: [name] for name in NAMES}  # No self-edge (self-vote)
            for s in sources:
                candidates = [u for u in names_todo if u not in excluded[s]]
                if not candidates:  # Failure of function call
                    break
                r = np.random.choice(candidates)
                targets.append(r)
                excluded[s].append(r)  # No double edge (double-vote)
                names_todo.remove(r)

        edges = list(zip(sources, targets))

        # Print
        num_rec: int = num_reciprocal_edges(edges)
        curr_perc = round(100 * num_rec / NUM_EDGES, 2)
        if curr_perc > perc:
            perc = curr_perc
            print(f"rec_check #{rec_check} num_reciprocal_edges = {num_rec} ({perc} %)")
        rec_check += 1

    log(edges)
    draw_graph(edges)


if __name__ == "__main__":
    run_main()