Christmas Lists

The challenge is to create one program that will accept as arguments (arrays of arrays) or on standard input (line-by-line, separated by commas) a collection of families and names, like so:

John,Anna
Mark,James
Elizabeth,Daniel,Isabelle
Ryan,Ruth


As well as two other arguments (two more arrays of pairs, as arrays) or on standard input (a blank line after the preceding input, followed by two comma-separated lists on two lines with an = separating pairings; see example) that represent the two previous years' Christmas lists:

John=Mark,James=Anna,Elizabeth=Ryan,...
John=Isabelle,Ryan=Elizabeth,Daniel=Mark,...


The function/program must return/output (in any format) a way that each person is assigned somebody to give a present to, following these rules:

1. A person cannot give a present to him or herself.
2. A person cannot give a present to anybody in his or her own family.
3. A person cannot be assigned the same person he or she was assigned in any of the two previous years.

If such a matching is impossible for every person, output/return null or nothing or something appropriate.

This is a code golf, so shortest code wins, but I'll also give a bounty to the code that runs fastest (on my computer, at least, though results shouldn't vary much).

• Are the gift assignments symmetric? The text doesn't say so, but using = to represent the assignments suggests it... – Keith Randall Jul 7 '12 at 6:05
• Shouldn't the number of people be guaranteed to be even? – Peter Taylor Jul 7 '12 at 6:13
• @KeithRandall: No, they aren't symmetric. – Ry- Jul 7 '12 at 13:35
• @PeterTaylor: No, because they aren't symmetric. (Dan=Marge,Marge=Carolyn,Carolyn=Don,Don=Bob,Bob=Dan) – Ry- Jul 7 '12 at 13:37
• @userunknown What, we can't prepare early for christmas? I like to buy my christmas cards in January in the sales. :-) Seriously though, I think -1 for being unseasonal is a little harsh. – Gareth Jul 7 '12 at 16:31

GolfScript, 90 characters

+:q;:f[]*:^[]:r\{.,{(^3${1=}%-f{2$\?)},~-q{(3$={-.}*;}/{.[[2$\]]4$|3$c;}%;;;}{;:r}if;}:c~r


The program does a simple recursive search on the names. It actually calculates all possible lists but saves them to a variable for output, so only the last one is returned.

The input/output is on the interpreter stack (first families then two previous years assignments), e.g.

#PREPARE INPUT
;
[["John" "Anna"]["Mark" "James"]["Elizabeth" "Daniel" "Isabelle"]["Ryan" "Ruth"]]
[["Ruth" "John"] ["Ryan" "Daniel"] ["Isabelle" "Mark"] ["Daniel" "Anna"] ["Elizabeth" "James"] ["James" "Elizabeth"] ["Mark" "Ryan"] ["Anna" "Isabelle"] ["John" "Ruth"]]
[["Ruth" "Anna"] ["Ryan" "Elizabeth"] ["Isabelle" "John"] ["Daniel" "James"] ["Elizabeth" "Mark"] ["James" "Daniel"] ["Mark" "Isabelle"] ["Anna" "Ruth"] ["John" "Ryan"]]

#PROGRAM
+:q;:f[]*:^[]:r\{.,{(^3${1=}%-f {2$\?)},~-q{(3$={-.}*;}/{.[[2$\]]4$|3$c;}%;;;}{;:r}if;}:c~r

#SHOW OUTPUT
p


prints the output

[["Ruth" "Elizabeth"] ["Ryan" "John"] ["Isabelle" "James"] ["Daniel" "Mark"] ["Elizabeth" "Anna"] ["James" "Ruth"] ["Mark" "Daniel"] ["Anna" "Ryan"] ["John" "Isabelle"]]
`