Giving Change with PostgreSQL
For one of my courses I wanted to create a task to learn about problem solving techniques using recursive common table expressions in PostgreSQL. So we want to make change change (giving back money from the till after a purchase). As a general algorithm we will do the following:
to make change for \(X\): Give out coin/bill for \(Y\) with \(Y \leq X\) and make change for \(X-Y\) until \(X=Y\)
First we create our denominations that we can give out. We will leave out the 1ct coin. This will be example later on, because this makes greedy algorithms (always give out the largest possible denominator) fail. If you want to give out 6ct and choose to give out 5ct first, then you can't make change for the remaining cent. So by leaving out the 1ct coin, we have to keep this in mind from the beginning.
CREATE TABLE denoms ( v NUMERIC(5,2) PRIMARY KEY );
INSERT INTO denoms VALUES
(100), (50), (20), (10), (5), (2), (1), (0.5), (0.2), (0.1), (0.05), (0.02);
Let us try out to give 17ct out first. Our initial recursive call will have the money we still have to give out, and a list (text) of denominations we already have given out. And then we just give out any denominations and print the one where all money is given out:
WITH RECURSIVE r AS (
SELECT 0.17 remaining, '' given
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v
FROM r JOIN denoms ON (denoms.v <= r.remaining)
)
SELECT given FROM r WHERE remaining = 0;
| given |
| ------------------------------------------ |
| , 0.02, 0.05, 0.10 |
| , 0.02, 0.10, 0.05 |
| , 0.05, 0.02, 0.10 |
| , 0.05, 0.10, 0.02 |
| , 0.10, 0.02, 0.05 |
| , 0.10, 0.05, 0.02 |
| , 0.02, 0.05, 0.05, 0.05 |
| , 0.05, 0.02, 0.05, 0.05 |
| , 0.05, 0.05, 0.02, 0.05 |
| , 0.05, 0.05, 0.05, 0.02 |
| , 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.05 |
| , 0.02, 0.02, 0.02, 0.02, 0.02, 0.05, 0.02 |
| , 0.02, 0.02, 0.02, 0.02, 0.05, 0.02, 0.02 |
| , 0.02, 0.02, 0.02, 0.05, 0.02, 0.02, 0.02 |
| , 0.02, 0.02, 0.05, 0.02, 0.02, 0.02, 0.02 |
| , 0.02, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
The main thing to notice here is, that we have each solution multiple times, as there is basically no order to us giving out the coins. Let's add to our algorithm the following: Once we have given out a denomination, we no longer give out larger denominations. This changes our recursive table to also include the largest denomination there is, and the join needs to take that into account:
WITH RECURSIVE r AS (
SELECT 0.17 remaining, '' given, (SELECT max(v) FROM denoms) largest
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v, denoms.v
FROM r JOIN denoms ON (denoms.v <= r.remaining AND denoms.v <= r.largest)
)
SELECT given FROM r WHERE remaining = 0;
| given |
| ------------------------------------------ |
| , 0.10, 0.05, 0.02 |
| , 0.05, 0.05, 0.05, 0.02 |
| , 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
This is now much nicer and faster. But the number of variants grows quite fast and with 86ct we already have over a hundred possible ways to make change. I mean, this is correct but overall not very useful.
So let's leave the realm of completeness and add to our algorithm, that we only ever try the two largest possible denominations and not all of them. Ideally, we would be using a subqery instead of the full denoms table, but we are not allowed to access r in the subqery. So something like this would not be allowed:
WITH RECURSIVE r AS (
SELECT 0.86 remaining, '' given, (SELECT max(v) FROM denoms) largest
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v, denoms.v
FROM r, (SELECT v FROM denoms WHERE denoms.v <= r.remaining AND denoms.v <= r.largest ORDER BY v DESC LIMIT 2) denoms
-- this does not work!
)
SELECT given FROM r WHERE remaining = 0;
Instead, we can write all the stuff under WHERE, filtering out exactly which kinds of denominations we actually want to give out:
WITH RECURSIVE r AS (
SELECT 0.86 remaining, '' given, (SELECT max(v) FROM denoms) largest
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v, denoms.v
FROM r, denoms WHERE denoms.v in (SELECT v FROM denoms WHERE v <= r.remaining AND denoms.v <= r.largest ORDER BY V DESC LIMIT 2)
)
SELECT given FROM r WHERE remaining = 0;
| given |
| ------------------------------------------------------------------------------------------------------------------------------------------------------------------ |
| , 0.50, 0.20, 0.10, 0.02, 0.02, 0.02 |
| , 0.50, 0.20, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.50, 0.10, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.20, 0.20, 0.02, 0.02, 0.02 |
| , 0.50, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.20, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.50, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.20, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.10, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.10, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.50, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.05, 0.05, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
| , 0.20, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02 |
Okay, this is still a lot. What we can alternatively do, is prevent taking a denomination that would need more than 5 of it for the remainder. That exclude the not-so-nice solutions:
WITH RECURSIVE r AS (
SELECT 0.86 remaining, '' given, (SELECT max(v) FROM denoms) largest
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v, denoms.v
FROM r JOIN denoms ON (denoms.v <= r.remaining AND denoms.v <= r.largest AND denoms.v*5 >= r.remaining)
)
SELECT given FROM r WHERE remaining = 0;
| given |
| ------------------------------------------------------------ |
| , 0.50, 0.20, 0.10, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.20, 0.20, 0.02, 0.02, 0.02 |
| , 0.50, 0.10, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.50, 0.20, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.20, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.50, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.10, 0.10, 0.10, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.20, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
| , 0.20, 0.20, 0.10, 0.10, 0.10, 0.05, 0.05, 0.02, 0.02, 0.02 |
And there we have it. That seems nice. Let's try out just a final larger example, with smaller maximum cardinality (3), just to check.
WITH RECURSIVE r AS (
SELECT 35.99 remaining, '' given, (SELECT max(v) FROM denoms) largest
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v, denoms.v
FROM r JOIN denoms ON (denoms.v <= r.remaining AND denoms.v <= r.largest AND denoms.v*3 >= r.remaining)
)
SELECT given FROM r WHERE remaining = 0;
| given |
| -------------------------------------------------------------------------- |
| , 20.00, 10.00, 5.00, 0.50, 0.20, 0.20, 0.05, 0.02, 0.02 |
| , 20.00, 10.00, 5.00, 0.50, 0.20, 0.10, 0.10, 0.05, 0.02, 0.02 |
| , 20.00, 10.00, 2.00, 2.00, 1.00, 0.50, 0.20, 0.20, 0.05, 0.02, 0.02 |
| , 20.00, 10.00, 2.00, 2.00, 1.00, 0.50, 0.20, 0.10, 0.10, 0.05, 0.02, 0.02 |
That seems nice.
alternatively, we can also additionally count the number of coins/bills given out and try to use the fewest:
WITH RECURSIVE r AS (
SELECT 119.99 remaining, '' given, (SELECT max(v) FROM denoms) largest, 0 cnt
UNION
SELECT r.remaining - denoms.v, given || ', ' || denoms.v, denoms.v, r.cnt + 1
FROM r JOIN denoms ON (denoms.v <= r.remaining AND denoms.v <= r.largest AND denoms.v*5 >= r.remaining)
)
SELECT given, cnt FROM r WHERE remaining = 0 ORDER BY cnt ASC LIMIT 5;
| given | cnt |
| --------------------------------------------------------------------------- | --- |
| , 100.00, 10.00, 5.00, 2.00, 2.00, 0.50, 0.20, 0.20, 0.05, 0.02, 0.02 | 11 |
| , 100.00, 5.00, 5.00, 5.00, 2.00, 2.00, 0.50, 0.20, 0.20, 0.05, 0.02, 0.02 | 12 |
| , 100.00, 10.00, 5.00, 2.00, 1.00, 1.00, 0.50, 0.20, 0.20, 0.05, 0.02, 0.02 | 12 |
| , 100.00, 10.00, 5.00, 2.00, 2.00, 0.50, 0.20, 0.10, 0.10, 0.05, 0.02, 0.02 | 12 |
| , 50.00, 50.00, 10.00, 5.00, 2.00, 2.00, 0.50, 0.20, 0.20, 0.05, 0.02, 0.02 | 12 |
And there we go, this is how we make change in PostgreSQL using the RECURSIVE keyword (it's actually more of a co-recursive thing, if you ask me) in Common Table Expressions.
Previous: How Many Boxes are on the Trailer?
Comments and Discussion is provided by Disqus. They are tracking site and user interaction. Please refer to their privacy policy for information about data usage and retention. If you still want to look at comments or comment yourself, enable disqus by clicking here.