#SQL30 Day 13: Permutations

Welcome to the SQL showdown series!

What is this and how does it work?

I'm committing to publishing a SQL challenge every day for 30 days. In each post I'll describe my solution to the last day's challenge. I'll follow that up with a full description of the challenge for the next day.

Write your own solution in the comments! Let's see who can come up with the most creative solutions.

Challenge #13: Permutations

This is a seemingly simple, yet somewhat tricky challenge for today.

Can you generate all of the permutations of a given set in SQL?

There is no table available on the sandbox server for today's challenge, but the source data is easy to create using something like the generate_series function in PostgreSQL.

For this challenge I'm using the set {1, 2, 3}. Here's an example of the output we should get:

Solution to Challenge #12: Greatest Discount

The key trick to solving yesterday's challenge is to think in terms of events, rather than ranges of times. In other words, a discount starting is an event, and a discount ending is an event. When a discount starts the overall cumulative rate rises, and conversely, the rate falls when a discount ends.

To break down a range into separate events we can use UNION ALL to combine queries that select the start and end dates.

SELECT start_date AS dt, rate FROM day12.discount
UNION ALL
SELECT end_date AS dt, -rate FROM day12.discount

Negating the rate in the second query will allow us to do a running total on the rates, thus giving the cumulative rate at each point in time.

Whenever a phrase like "running total" or "rolling average" appears, it's a safe bet that window functions are part of the solution. Let's look at how we can combine the first query with a window function to find the cumulative discount rate:

SELECT sum(rate) OVER (ORDER BY dt) AS cumulative_disc, dts.dt FROM (
  SELECT start_date AS dt, rate FROM day12.discount
  UNION ALL
  SELECT end_date AS dt, -rate FROM day12.discount
) AS dts ORDER BY cumulative_disc DESC;

The ORDER BY within the OVER clause limits the sum to the current row and all rows prior to it (sorted by date). From there it's just a matter of sorting the entire query to get the greatest possible discount.

Good luck!

Have fun, and I can't wait to see what you come up with! I'll be back tomorrow with a solution to this problem and a new challenge.