Family Gifts Family Gifts

Every Christmas in my family, each of us gives a present to only one other person. To organize who should offer a gift to whom (I call it the chain of presents), we introduced a few rules:

- There should be a single chain where every person in the family is present,
- Couples should not give to one another,
- Every person should give a gift to a different person than they had in previous years

So the problem would be to find and list the longest list of chains of presents. For example in a family {a,b,c,d} with couples=({a,b},{c,d}): [[a,c,b,d],[a,d,b,c]].

You are given a set of family member names and a list of couples in this family. Find the maximum number of chains with all family members. Gift chains should be represented as a list of names where i-th gives a present to i+1-th and the last person in the list to the first.

Input: Names of family members as a set of strings. Couple list as a tuple of sets with two strings in each.

Output: The longest list of gift chains as a list/tuple of lists/tuples with strings.


How it is used: This is a combinatorial task that can be useful for scheduling.


len(couples) <= 7