Secret Santa Pairing

Graph Algorithm Backtracking

Problem Description

It's that time of year again! In a Secret Santa event, each participant is randomly assigned another participant to whom they give a gift. Your task is to write a function that generates a valid Secret Santa pairing.

Requirements

  1. Self-assignment Forbidden: No participant should be assigned to themselves.
  2. Disallowed Pairings: In addition to the self-assignment rule, there may be specific pairs that are not allowed. For example, if two individuals are a pair (such as spouses), they must not be assigned to each other. The input will include a list of these forbidden pairings.
  3. Complete Assignment: Every participant must be assigned exactly one recipient, and each recipient must be assigned to exactly one participant.

Input

  • A list of unique participant names (strings).
  • A list of forbidden pairings. Each pairing can be represented as a two-element array (or tuple) of names. These pairings are bidirectional (if [A, B] is forbidden, then [B, A] is also forbidden).

Output

  • Return a valid assignment mapping each participant to a recipient such that all of the above requirements are met.

If no such assignment is possible, your function should clearly indicate that (e.g., by returning an empty structure or an appropriate error message).

Example

For instance, given the participants:

["Alice", "Bob", "Charlie", "Dana"]

and the forbidden pairings:

[["Alice", "Bob"], ["Charlie", "Dana"]]

A valid output might be an object/dictionary like:

{
  "Alice": "Charlie",
  "Bob": "Dana",
  "Charlie": "Bob",
  "Dana": "Alice"
}

Note that this output respects both the self-assignment rule and ensures that none of the forbidden pairings appear.

Constraints

  • Optimize for efficiency if the number of participants is large.
  • Assume the list of participants is non-empty.

Happy coding and good luck with your festive algorithm design!