You're seating guests along one side of a long table. Some pairs of guests are feuding, and two feuding guests must never sit next to each other (anywhere else is fine).
Write seatings(guests: list[str], feuds: list[tuple[str, str]]) -> list[list[str]] that returns every left-to-right order of all the guests in which no two neighbours feud. The orders can come back in any order (the tests sort them).
seatings(["ann", "bo", "cy"], [("ann", "bo")])
# [["ann", "cy", "bo"], ["bo", "cy", "ann"]] cy has to sit in the middle
seatings(["ann", "bo"], [("bo", "ann")]) # [] feuds work both ways
seatings([], []) # [[]] one way to seat nobody
0 <= len(guests) <= 8; guest names are distinct. Each feud names two different guests from the list; a pair may be listed more than once.- Write the recursion yourself; don't use
itertools.
Show hint
turn feuds into a set of frozensets (or a dict of sets) so "do these two feud?" is O(1); then backtrack(row) tries each unused guest, skips them if they feud with row[-1], and otherwise appends, recurses, and pops. Skipping a feuding guest right away prunes every order that would start that way, instead of building full orders and filtering them afterwards.