Computer Science I Program $3$: Where to Sit? $($Recursion$)$

Please Check Webcourses for the Due Date

Please read the whole assignment before you start coding

Objective

Give practice with recursion.

Give practice with functions in $C.$

Give practice with creating a design for a program without a given list of functions or structs.

Background Story

You and your friends are planning to get together to attend a movie! However, there are a few restrictions on where everyone can sit:

Some people don't want to sit next to each other.

Everyone should have access to popcorn! $($This means that for each person, either they bought popcorn, or the person directly to their left or the person directly to their right did.$)$

For example, imagine that there are five people who want to attend the movie: Alia, Belinda, Carlos, Danica and Edward, where only Alia and Edward buy popcorn. In addition, Alia and Carlos can't sit next to each other and Belinda and Edward can't sit next to each other. Given these restrictions, they can sit in a single row in $10$ possible orders.

$\backslash$table$[[$Alia$,$Belinda,Carlos,Edward,Danica$],[$Alia$,$Belinda,Danica,Edward,Carlos$],[$Belinda$,$Alia,Danica,Carlos,Edward$],[$Belinda$,$Alia,Danica,Edward,Carlos$],[$Carlos$,$Edward,Danica,Alia,Belinda$],[$Carlos$,$Edward,Danica,Belinda,Alia$],[$Danica$,$Alia,Belinda,Carlos,Edward$],[$Danica$,$Edward,Carlos,Belinda,Alia$],[$Edward$,$Carlos,Belinda,Alia,Danica$],[$Edward$,$Carlos,Danica,Alia,Belinda$]]$

Problem

Write two related programs where, given the list of people who are going to the movies together, the pairs of people who can't sit next to each other, and the list of people who are buying popcorn, determines the two following things:

$(1)$ Program $1-$ the number of different orderings $($permutations$)$ of the movie attendees that satisfy all the restrictions.

$(2)$ Program $2-$ the first ordering $($in lexicographical order$)$ of the movie attendees that satisfy all the restrictions.