Secret Santa-generator

Sådan fungerer lodtrækningen, og hvad der er i et link

Hver person må trække alle undtagen sig selv og dem, du har holdt fra dem. »Hinanden« fjerner begge retninger mellem to personer; »én vej« fjerner kun den ene. Før noget trækkes, tjekker generatoren, om der overhovedet findes en lodtrækning, der overholder alle reglerne. Med ét navn hver er det et matchingproblem — kan hver person få et forskelligt navn, de må trække — og det besvares præcist, ikke ved at prøve og håbe. Når svaret er nej, nævner siden de personer, det skyldes: en gruppe af givere, som tilsammen må trække færre navne, end der er personer i gruppen. Halls giftesætning (Hall's marriage theorem) siger, at en lodtrækning findes, præcis når ingen sådan gruppe findes, så at nævne gruppen er at nævne årsagen.

Med ét navn hver er lodtrækningen en blanding. Hele listen blandes med browserens kryptografiske tilfældighedsgenerator, og blandingen beholdes kun, hvis hver person er landet på en, de må trække; ellers blandes den igen, op til tyve tusind gange. Ved kun at beholde de blandinger, der består, får hver gyldig lodtrækning præcis den samme chance. Kun når reglerne efterlader så få gyldige lodtrækninger, at alle tyve tusind blandinger fejler, falder siden tilbage på en tilfældig søgning, som altid finder en, men ikke lover hver lodtrækning lige chancer.

Med to navne hver er tjekket et flowproblem: alle giver to, alle modtager to, og ingen trækker den samme person to gange. Selve lodtrækningen er to runder af blandingen med ét navn, hvor den anden runde ikke må gentage den første. Det kommer tæt på lige chancer for hver gyldig lodtrækning med to navne uden at være helt lige, og det siger vi hellere end at runde op.

Tallet i teksten under værktøjet er almindelig regning. Når alle i en gruppe trækker ét navn fra en hat, er andelen af lodtrækninger, hvor ingen får sit eget navn, antallet af fixpunktsfrie permutationer (derangements) divideret med antallet af rækkefølger: 9 af 24 for fire personer, 44 af 120 for fem, 14.833 af 40.320 for otte. Fra fire personer og op ligger den mellem 36 % og 38 %, og den ender på én divideret med e, cirka 36,8 %.

Hvert link bærer én persons lodtrækning: begivenhedens navn, deres eget navn, navnet eller navnene på dem, de køber til, med eventuelle hints, du har tilføjet, budgettet, datoen, din note, en lodtrækningskode på fire tegn og det minut, lodtrækningen blev lavet. Det er forvansket, så et navn ikke kan læses ved et hurtigt blik i en beskedforhåndsvisning. Det er ikke kryptering: enhver, der åbner et link, ser, hvad det indeholder, så send kun hver person deres eget. De printede kort bærer det samme link som en QR-kode, med fejlkorrektionsniveau M, som QR-standarden angiver kan gendanne omkring 15 % af et beskadiget symbol, eller niveau L, omkring 7 %, til et link, der er for langt til M. Grænsen på fyrre personer er vores eget valg — over den bliver ringen af navne og siden med kort ulæselige. Kalenderfilen på visningssiden indeholder én heldagsbegivenhed på byttedagen med en påmindelse en uge før, og den nævner dagen og budgettet, men aldrig personen. Navnene, reglerne, detaljerne og lodtrækningen gemmes i denne browser, så arrangøren kan sende et mistet link igen; der er ingen konto.

Hvor tallene kommer fra

1. 1. On Representatives of Subsets (Hall's marriage theorem) — P. Hall, Journal of the London Mathematical Society, 1935
2. 2. A000166: Subfactorial or rencontres numbers, or derangements — The On-Line Encyclopedia of Integer Sequences
3. 3. ISO/IEC 18004:2015 — QR Code bar code symbology specification — International Organization for Standardization
4. 4. Crypto: getRandomValues() method — MDN Web Docs, Mozilla

Hvert tal ovenfor er aflæst i den kode, der kører på denne side. Hvor et tal er vores eget skøn og ikke et offentliggjort tal, siger noten det og henviser ikke til nogen kilde. Metoden sidst tjekket 28. september 2026.