Christmas Lists

Question

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).

Answer 1

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"]]