admin@onlinelearningcenter.in (+91) 7 999 01 02 03

Suraz's Summer Vacation Plans

Ayush Dixit
15 Posts

During the summer break, Suraz is planning to go for a summer vacation and decided on the cities that he and his family want to visit. But he has not finalized in which order he wants to visit them yet. Please help Suraz to solve this dilemma and help him with all the possible orders he can visit these cities. Note that he neither wants to visit the same city again nor he wants to skip any city in his travel plan. 

Write a SQL query to list out all different possible orders suraz can visit these cities.

We have been given a City table having h City_Name as an entity.

Sample Input:-

 

Sample Output:-

 
id travel_plan
1 Goa -> Manali -> Ooty -> Shimla
2 Goa -> Manali -> Shimla -> Ooty
3 Goa -> Ooty -> Manali -> Shimla
4 Goa -> Ooty -> Shimla -> Manali
5 Goa -> Shimla -> Manali -> Ooty
6 Goa -> Shimla -> Ooty -> Manali
7 Manali -> Goa -> Ooty -> Shimla
8 Manali -> Goa -> Shimla -> Ooty
9 Manali -> Ooty -> Goa -> Shimla
10 Manali -> Ooty -> Shimla -> Goa
11 Manali -> Shimla -> Goa -> Ooty
12 Manali -> Shimla -> Ooty -> Goa
13 Ooty -> Goa -> Manali -> Shimla
14 Ooty -> Goa -> Shimla -> Manali
15 Ooty -> Manali -> Goa -> Shimla
16 Ooty -> Manali -> Shimla -> Goa
17 Ooty -> Shimla -> Goa -> Manali
18 Ooty -> Shimla -> Manali -> Goa
19 Shimla -> Goa -> Manali -> Ooty
20 Shimla -> Goa -> Ooty -> Manali
21 Shimla -> Manali -> Goa -> Ooty
22 Shimla -> Manali -> Ooty -> Goa
23 Shimla -> Ooty -> Goa -> Manali
24 Shimla -> Ooty -> Manali -> Goa

 

My Solution:-

This solution is implemented using recursive CTE as we need to find all the possible combinations. As we need to have a plan with all the four cities, we are filtering only the plan that has four cities.

Before jumping into the final query Let's discuss What is Recursive CTE and how it works?

Recursive CTE:

A recursive CTE references itself. It returns the result subset, then it repeatedly (recursively) references itself, and stops when it returns all the results. The syntax for a recursive CTE is not too different from that of a non-recursive CTE.

Recursive CTE Syntax:

WITH RECURSIVE cte_name AS (
cte_query_definition (the anchor member)

UNION ALL

cte_query_definition (the recursive member)
)

SELECT * FROM cte_name;
 

At the beginning of your, CTE is the WITH clause. However, if you want your CTE to be recursive, then after WITH you write the RECURSIVE keyword. Then it’s business as usual: AS is followed by the parentheses with the CTE query definition. This first query definition is called the anchor member.

To connect the anchor member with the recursive member, you need to use the UNION or UNION ALL command. The recursive member is, obviously, the recursive part of CTE that will reference the CTE itself. You’ll see how it works in an example very soon. 

Recursive CTEs are used primarily when you want to query hierarchical data or graphs. This could be a company’s organizational structure, a family tree, a restaurant menu, or various routes between cities. 

Now that we have understood how recursive CTEs work, let’s look into the final solution now.

Final Query:

SET @total_cities = (SELECT COUNT(1) FROM City);
WITH RECURSIVE travel (travel_plan, level) AS
(
SELECT City.City_Name AS travel_plan,
1 AS level FROM City

UNION ALL

SELECT CONCAT(travel.travel_plan ,' -> ' ,City.City_Name) AS travel_plan,
level + 1
FROM City, travel
WHERE travel.level < @total_cities AND POSITION(City.City_Name IN travel.travel_plan) = 0

)

SELECT row_number() OVER(ORDER BY travel_plan) AS id, travel_plan
FROM travel WHERE level = @total_cities ORDER BY id;

 

Explanation:-

The CTE starts with WITH RECURSIVE, followed by its name and the query definition. This time, I’ll use the anchor member of the recursive query to create some data. The columns are leveltravel_plan. This is the point(with level =1) at which I want the recursion to start.

The UNION ALL connects this with the recursive member. This SELECT statement will select the city, concatenate the cities with the travel plan, and the query will increase the level column by one with every recursion. It will do that for every city visited.The recursion will be performed for up to four cities (i.e. until it reaches the condition WHERE level< 4).To achieve all that, I’ve joined the CTE with the table travel.

Then comes the SELECT a statement that pulls data from the CTE. It will select all the possible travel_plan ordered by id in ascending order.

 

Thanks for reading. I hope you enjoyed this fun little case study - it was fun for me to create!. You can also share your approach to solve this problem.

 

 

 

Published By : Ayush Dixit
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Comments