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.

Input

The first line of input contains two positive integers: $)n(10,$ the number of people attending the movie, and $)p(n,$ the number of pairs of people who do not want to sit next to each other.

The next $n$ lines will contain the information about each of the people attending the movie, with one person described per line. These lines will describe the people in alphabetical order. Each of these lines will have the following format:

NAME $,\frac{0}{1}$

Each name will be an uppercase alphabetic string with no more than $19$ characters. If the number $0$ is on the line, this indicates that that person does not have popcorn. If the number $1$ is on the line, this indicates that that person does have popcorn.

The following $p$ lines will each contain a pair of names, indicating two people who do not want to sit next to each other. It is guaranteed that each of the $2p$ names appearing in this section will be one of the $n$ names listed previously as the movie attendees. Secondly, it's guaranteed that the two names on a single line will be distinct.

Output $($for Program $1)$

On a single line, simply output the total number of valid orderings of the people attending the movie sitting together in a single row, from left to right. It is guaranteed that the input data will be such that this value will be a positive integer.

Output $($for Program $2)$

Output, with one name per line, the first lexicographical valid ordering of the people attending the moving sitting together in a single row, from left to right. In lexicographical ordering, all lists starting with name$1$ will come before all lists starting with name $2$ if name$1$ comes before name $2$ alphabetically. Specifically, given two lists, to determine which one comes first lexicographically, find the first corresponding name on both lists that don't match. Which ever name comes first alphabetically, is the list that comes first in lexicographical order. $($Hint: since the given names are already in alphabetical order, the permutation algorithm shown in class will naturally evaluate the permutations in lexicographical order. Thus, to solve this program, the first valid solution found while running the algorithm will be the correct answer.$)$

$\backslash$table$[[$Sample Input,Sample Output $1,$Sample Output $2],[52,10,$ALIA$],[$ALIA $1$ BELINDA,,$],[$BELINDA $0,,$CARLOS$],[$CARLOS $0,,$EDWARD$],[$DANICA $0,,$DANICA$],[$EDWARD $1,,],[$ALIA CARLOS,,$],[$BELINDA EDWARD,,$],[83,10248,$ALEX$],[$ALEX $1,,$ELLIE$],[$ELLIE $1,,$FRANKLYN$],[$FRANKLYN $0,,$JAMELLE$],[$JAMELLE $0,,$MARTY$],[$MARTY $1,,$SRI$],[$PRI $1,,$WES$],[$SAMANTHA $1,,],[$WES $0,,],[$ALEX WES,,$],[$ELLIE MARTY,,$],[$ELLIE WES,,MEGAN$],[5,,$JACQUELINE$],[$ANEESHA $0,,$ARTHUR$],[$ARTHUR $0,,$MATTHEW$],[$JACQUELINE $1,,],[$MATTHEW $1,,],[$MEGAN $0,,],[$ROBINSON $0,,],[$ROBIN