sint, math, handwaiving
HELSINKI - Nadat Sinterklaas ons in Madrid ternauwernood ontkomen was, hopen we 'm volgende week hier in Helsinki te vinden. We proberen het traditionele feest ook buiten de Nederlandse landsgrenzen te populariseren, om te beginnen in Finland. We hebben dan ook al een feestelijke avond gepland, volgende dinsdag 5 december, waarbij de gasten elk een lootje krijgen met daarop de naam van de degene voor wie ze een cadeautje moeten kopen. Met een gedicht, uiteraard.

de laatste lootjes

Het trekken van de lootjes is natuurlijk bij uitstek een taak voor de computer. We kunnen het resultaat van het lootjestrekken voorstellen als een relatie R, met elementen (x,y), waarbij (x,y) betekent "x krijgt het lootje van y". Ik heb in eerste instantie twee eisen aan het eindresulaat, R:

1. niemand kan zijn eigen lootje trekken: (x,y) ∈ R → x ≠ y (irreflexief);
2. als x het lootje trekt voor y, dan mag y niet het lootje trekken voor x: (x,y) ∈ R → (y,x) ∉ R (asymmetrisch).

De eerste eis is vanzelfsprekend, en met de twee eis probeer ik de deelnemers wat meer met elkaar te verbinden;

Hoe kan ik dit probleem oplossen? Het resultaat R bestaat uit n elementen, en ik moet kiezen uit een totaal aantal mogelijkheden van n!. Bij 10 deelnemers zijn er 362880 mogelijkheden, zo vertelt emacs mij:

(defun fac (n) (if (= 1 n) n (* n (fac (- n 1)))))
(fac 10)
=> 3628800

Da's behoorlijk veel! Ik kan de lootjes voorstellen als een lijst met namen a,b,c,d,e. Als ik die lijst 'randomiseer' (ie. schud), krijg ik bijvoorbeeld:

b

a

d

e

c

Nu neem ik een kopie van die lijst, en verschuif de elementen cyclisch een plaats naar rechts, en krijg dan:

c

b

a

d

e

De paren worden dan eenvoudig gevormd uit de corresponderende kolommen in de twee lijsten, dus

R = {(b,c), (a,b), (d,a), (e,d), (c,e)}, ofwel (x,(x+1) mod n)

Kan ik er nu zeker van zijn dat deze lijst aan mijn eisen (1) en (2) voldoet?

1. Een paar wordt beschreven als (x,(x+1) mod n); derhalve is de vraag wanneer geldt: x ≠ (x + 1) mod n. Dat geldt altijd, zolang n > 1;
2. Eis (2) stelt dat (x,y) ∈ R → (y,x) ∉ R. Laten we eens bekijken wanneer (y,x) wel ∈ R. Voor y kunnen we x+1 mod n invullen, en we krijgen dan dus (x+1+1 mod n,x). Aangezien dat paar moet voldoen aan (x, x + 1 mod n) geldt dat voor het eerste element van het paar: (x + 2) mod n = x, wat alleen oplossingen heeft voor n > 2. Het tweede element gaat zoals bij eis (1); eindconclusie: eis 2 wordt voldaan, zolang n > 2.

implementatie

Ik wilde de implementatie eigenlijk in Haskell (zie onder) doen, maar kwam uiteindelijk toch bij Ruby terecht. Da's simpel; de kern bestaat uit twee simpele functies, shuffle 'schudt' mijn lijst met namen, en rcs_pairs genereert de lijst met paren uit de corresponderende lijst en de verschoven lijst.

srand # seed the random num generator

# shuffle the lst in random order
def shuffle (lst)
return lst.sort{|x,y| 0.5 <=> rand }
end

# make a list of pairs from a list
# by pairing each item n in the list with item n
# in a n-element cyclically shifted version of the same list
def rcs_pairs (lst,n)
pairs = []
0.upto((lst.length)-1) do |i|
pairs.push([lst[i], lst[(i+n)%lst.length]])
end
return pairs
end

De invoer voor het programma komt vanaf stdin, een naam per regel:

donald
katrien
george
barbara
peter
lois
rupert

We kunnen die name simpel in een lijst lezen, en de resultaten printen:

lst = []
# read strings from stdin
while gets
lst.push($_.chomp)
end

# give me the results!
tickets = rcs_pairs(shuffle(lst), 1)
tickets.each {|n| print "#{n[0]} -> #{n[1]}\n"}

en klaar is kees..., de uitvoer:

% ruby tickets.rb <> rupert
rupert -> donald
donald -> george
george -> barbara
barbara -> peter
peter -> katrien
katrien -> lois

Of? Ik bedacht me nog een derde nuttige eis: partners mogen elkaar niet kiezen. Als bijv. in het bovenstaande george en barbara partners zijn, zouden ze niet elkaars lootje mogen trekken. Oftewel, eis nummer 3:

3. (x,y) ∈ R → not P(x,y) , waarbij het predicaat P(x,y) betekent dat x en y partners (in de intermenselijke zin) zijn.

hack

Dat zou ik natuurlijk ook wel in mijn model kunnen opnemen, maar... ik ben geen drs. of dr. maar slechts een eenvoudige ir. en derhalve zoek ik naar een eenvoudige, werkende oplosing... Mijn hack is de volgende: normaalgesproken verwacht mijn program een naam per regel vanaf stdin. Als ik nu eens de beide partners op dezelfde regel zet? De invoer ziet er dan uit als:

donald katrien
george barbara
peter lois
rupert

Ruby staat heterogene lijsten toe, en ik kan dus in plaats van enkelvoudige namen daarnaast ook (a,b)-paren in dezelfde lijst zetten; de inleesroutine wordt nu:

lst = []
# read strings from stdin, version 2
while gets
#lst.push($_.chomp.split)
end

(de 'split' splitst de namen in paren)

Vervolgens sorteer ik de lijst zoals tevoren, en dan 'flatten' ik de lijst. Dat wil zeggen dat ['rupert', ['peter', 'lois'] .... ] nu gewoon ['rupert', 'peter', 'lois' ... ] wordt. Maar omdat ik de dat pas na het schudden doe, weet ik zeker dat de beide partners nog steeds naast elkaar staan in de lijst.

De rest van de oplossing ligt voor de hand: in plaats van de tweede lijst nu een plek te verschuiven, verschuif ik 'm twee plekken. Dan kan niemand meer het lootje van zijn of haar partner trekken (zolang n > 3, analoog aan wat ik boven aannemelijk maak):

# print the pairs, version 2
tickets = rcs_pairs(shuffle(lst).flatten,2)
tickets.each {|n| print "#{n[0]} -> #{n[1]}\n"}

Het totale script wordt dan:

#!/usr/bin/ruby
#Time-stamp: <2006-11-28>

# script that takes a list of n newline-separated strings from stdin;
# and print n pairs P of those names, with the following properties:
#
# (a,b) -> a != b          ,n > 1: no element is paired with itself
# (a,b) E R -> (b,a) ! E R ,n > 2: ie. if (a,b) is part of the set of pairs,
#                                  then (b,a) is not         
# (a,b) are not in some human relationship;
# a relationship is indicated by having the two names on the same row
# in the input (separated by a ' '), and the script will make sure that
# (a,b) !E R and (b,a) !E R


srand # seed the random num generator

# shuffle the lst in random order
def shuffle (lst)
return lst.sort{|x,y| 0.5 <=> rand }
end

# make a list of pairs from a list
# by pairing each item n in the list with item n
# in a one-element cyclically shifted version of the same list
def rcs_pairs (lst,n)
pairs = []
0.upto((lst.length)-1) do |i|
pairs.push([lst[i], lst[(i+n)%lst.length]])
end
return pairs
end

lst = []
# read strings from stdin
while gets
lst.push($_.chomp.split)
#lst.push($_.chomp)
end

# print the pairs
#tickets = rcs_pairs(shuffle(lst),1)
tickets = rcs_pairs(shuffle(lst).flatten, 2)
tickets.each {|n| print "#{n[0]} -> #{n[1]}\n"}

En dat geeft me de gewenste lijst:

% ./tickets.rb <> peter
katrien -> lois
peter -> george
lois -> barbara
george -> rupert
barbara -> donald
rupert -> katrien

Terzijde: ik wilde dit eigenlijk in Haskell implementeren (met hugs), maar dat bleek wat lastig - eigenlijk om een enkele reden: het verkrijgen van random-getallen in Haskell is niet mogelijk zonder in te gaan op monads. Het opvragen van een random-getal verandert echter de toestand (entropie etc.) van psuedo-randomgenerator, en aangezien puur-functionele talen zoals Haskell nogal nerveus worden van dit soort side-effects, heeft men het monad-concept geïntroduceerd. Maar dat bewaar ik voor een andere keer...
-- djcb @ 00:40 | 0 comments