Constructing a random Hamiltonian Cycle (Secret Santa)
I'm not sure what you mean by an efficient algorithm, but the problem of finding any Hamiltonian path is NP-complete, which means that it is very unlikely that a polynomial time algorithm exists for your problem.

If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of the people. Remove all permutations from the list that do not form a Hamiltonian cycle and do not satisfy your additional constraints. The time and space complexity is $O(n! n)$. Then pick a random permutation from the list.