def count_crossings_and_nestings(arcs): n = len (arcs) // 2 crossings = 0 nestings = 0 for i in range(2 * n): for j in range(i + 1, 2 * n): if arcs [i] [0] < arcs [j] [0] < arcs [i] [1] < arcs [j] [1]: crossings += 1 elif arcs [i] [0] > arcs [j] [0] > arcs[i] [1] > arcs[j][1]: crossings += 1 elif arcs[i][0] < arcs [j] [0] < arcs [j] [1] < arcs [i] [1]: nestings += 1 elif arcs [i] [0] > arcs [j] [0] > arcs [i] [1] > arcs [j][1]: nestings += 1 return crossings, nestings #Test cases test_cases=[ [], [(0,1)], [(0,1),(2,3)], [(0,3), (1,2)], [(0,2), (1,3)] ] # Empty set of arcs # Single arc # Two non-overlapping arcs # Two overlapping arcs # Two nested arcs for i, arcs in enumerate(test_cases, 1): crossings, nestings = count_crossings_and_nestings(arcs) print (f"Test case {i}:") print (f"Number of arcs: {len(arcs)}") print (f"Number of crossings: {crossings}") print (f"Number of nestings: {nestings}") print() Explanation below: {} (empty set of arcs): The output can be defined as (0, 0). {(0, 1)} (single arc): The output can be defined as (0, 0) because there are no crossings or nestings. {(0, 1), (2, 3)} (two non-overlapping arcs): The output can be defined as (0, 0) because there are no crossings or nestings. {(0, 3), (1, 2)} (two overlapping arcs): The output can be defined as (1, 0) because there is one crossing but no nestings. {(0, 2), (1, 3)} (two nested arcs): The output can be defined as (0, 1) because there are no crossings but one nesting. The output matches the expectations for all the test cases. Therefore, the function is working.
def count_crossings_and_nestings(arcs): n = len (arcs) // 2 crossings = 0 nestings = 0 for i in range(2 * n): for j in range(i + 1, 2 * n): if arcs [i] [0] < arcs [j] [0] < arcs [i] [1] < arcs [j] [1]: crossings += 1 elif arcs [i] [0] > arcs [j] [0] > arcs[i] [1] > arcs[j][1]: crossings += 1 elif arcs[i][0] < arcs [j] [0] < arcs [j] [1] < arcs [i] [1]: nestings += 1 elif arcs [i] [0] > arcs [j] [0] > arcs [i] [1] > arcs [j][1]: nestings += 1 return crossings, nestings #Test cases test_cases=[ [], [(0,1)], [(0,1),(2,3)], [(0,3), (1,2)], [(0,2), (1,3)] ] # Empty set of arcs # Single arc # Two non-overlapping arcs # Two overlapping arcs # Two nested arcs for i, arcs in enumerate(test_cases, 1): crossings, nestings = count_crossings_and_nestings(arcs) print (f"Test case {i}:") print (f"Number of arcs: {len(arcs)}") print (f"Number of crossings: {crossings}") print (f"Number of nestings: {nestings}") print() Explanation below: {} (empty set of arcs): The output can be defined as (0, 0). {(0, 1)} (single arc): The output can be defined as (0, 0) because there are no crossings or nestings. {(0, 1), (2, 3)} (two non-overlapping arcs): The output can be defined as (0, 0) because there are no crossings or nestings. {(0, 3), (1, 2)} (two overlapping arcs): The output can be defined as (1, 0) because there is one crossing but no nestings. {(0, 2), (1, 3)} (two nested arcs): The output can be defined as (0, 1) because there are no crossings but one nesting. The output matches the expectations for all the test cases. Therefore, the function is working.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
When we want to write Python code to count the number of crossings and nestings of an arc diagram,an example is attached
Question: For diagrams with three arcs, there are 15 possibilities. Find one for which the function count_crossings_and_nestings provides a wrong result. Print the result and draw the corresponding diagram.
![def count_crossings_and_nestings(arcs):
n = len (arcs) // 2
crossings = 0
nestings = 0
for i in range(2 * n):
for j in range(i + 1, 2 * n):
if arcs [i] [0] < arcs [j] [0] < arcs [i] [1] < arcs [j] [1]:
crossings += 1
elif arcs [i] [0] > arcs [j] [0] > arcs[i] [1] > arcs[j][1]:
crossings += 1
elif arcs[i][0] < arcs [j] [0] < arcs [j] [1] < arcs [i] [1]:
nestings += 1
elif arcs [i] [0] > arcs [j] [0] > arcs [i] [1] > arcs [j][1]:
nestings += 1
return crossings, nestings
#Test cases
test_cases=[
[],
[(0,1)],
[(0,1),(2,3)],
[(0,3), (1,2)],
[(0,2), (1,3)]
]
# Empty set of arcs
# Single arc
# Two non-overlapping arcs
# Two overlapping arcs
# Two nested arcs
for i, arcs in enumerate(test_cases, 1):
crossings, nestings =
count_crossings_and_nestings(arcs)
print (f"Test case {i}:")
print (f"Number of arcs: {len(arcs)}")
print (f"Number of crossings: {crossings}")
print (f"Number of nestings: {nestings}")
print()
Explanation below:
{} (empty set of arcs): The output can be defined as (0, 0).
{(0, 1)} (single arc): The output can be defined as (0, 0) because there are no crossings or nestings.
{(0, 1), (2, 3)} (two non-overlapping arcs): The output can be defined as (0, 0) because there are no crossings or nestings.
{(0, 3), (1, 2)} (two overlapping arcs): The output can be defined as (1, 0) because there is one crossing but no nestings.
{(0, 2), (1, 3)} (two nested arcs): The output can be defined as (0, 1) because there are no crossings but one nesting.
The output matches the expectations for all the test cases. Therefore, the function is working.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F033c0d82-90fb-4c58-9b03-1325bfffdb8d%2F7f83af6d-b25b-48e0-a56f-15af3579d0e7%2Fywassi_processed.png&w=3840&q=75)
Transcribed Image Text:def count_crossings_and_nestings(arcs):
n = len (arcs) // 2
crossings = 0
nestings = 0
for i in range(2 * n):
for j in range(i + 1, 2 * n):
if arcs [i] [0] < arcs [j] [0] < arcs [i] [1] < arcs [j] [1]:
crossings += 1
elif arcs [i] [0] > arcs [j] [0] > arcs[i] [1] > arcs[j][1]:
crossings += 1
elif arcs[i][0] < arcs [j] [0] < arcs [j] [1] < arcs [i] [1]:
nestings += 1
elif arcs [i] [0] > arcs [j] [0] > arcs [i] [1] > arcs [j][1]:
nestings += 1
return crossings, nestings
#Test cases
test_cases=[
[],
[(0,1)],
[(0,1),(2,3)],
[(0,3), (1,2)],
[(0,2), (1,3)]
]
# Empty set of arcs
# Single arc
# Two non-overlapping arcs
# Two overlapping arcs
# Two nested arcs
for i, arcs in enumerate(test_cases, 1):
crossings, nestings =
count_crossings_and_nestings(arcs)
print (f"Test case {i}:")
print (f"Number of arcs: {len(arcs)}")
print (f"Number of crossings: {crossings}")
print (f"Number of nestings: {nestings}")
print()
Explanation below:
{} (empty set of arcs): The output can be defined as (0, 0).
{(0, 1)} (single arc): The output can be defined as (0, 0) because there are no crossings or nestings.
{(0, 1), (2, 3)} (two non-overlapping arcs): The output can be defined as (0, 0) because there are no crossings or nestings.
{(0, 3), (1, 2)} (two overlapping arcs): The output can be defined as (1, 0) because there is one crossing but no nestings.
{(0, 2), (1, 3)} (two nested arcs): The output can be defined as (0, 1) because there are no crossings but one nesting.
The output matches the expectations for all the test cases. Therefore, the function is working.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 1 images
Similar questions
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education