November 17, 2013 at 2:53 pm
There's an often mentioned "problem" which is sometimes used to help in teaching kids to understand combinations, but more often just used for fun. The goal is to work out how many different amounts of money can be made up by using a non-empty subset of some given set of coins. I imagine most people will have come acoss this at least once.
Recently I came across it again in a social context, and decided to write a program to solve it. SQL seemed a reasonable language to do it in. But I ran into difficulties: as far as I can tell, the recursive CTE capability in SQL isn't up to this problem. Of course it's easy to write a loop but that offends my sense of esthetics and anyway it runs like a crippled snail. Given a limiting number of coin denominations (and a limit on the number of coins of each denomination) I can write a single query to solve all instances of the problem that don't have more different denominations than that limiting number and don't have more coins than allowed. But I can't get the general solution, with no reasonable restriction on teh number of denominations or on the number of coins.
I think I must be missing something - surely recursive CTEs are powerful enough to permit a general solution of this problem as a single query? Can anyone tell me how to do that?
Just so you can see where I'm at, I wrapped the code to handle up to 8 denominations and up to 5000 coins of each value in a inline table-valued udf which takes a table of a defined type as a parameterbelow:-
/-- This code assumes that there is a database called playpen which contains a schema called play.
-- It puts verious a type definition and a udf into that schema.
use playpen
go
-- first create the type used for coin sets:
create type play.coinlist as table(val int, ccount int);
-- now create the UDF
create function play.coinsums (@coins play.coinlist READONLY)
returns table as
return
with tally as (select 0 as I union all select top 5000 row_number() over(order by y.object_id)
from master.sys.all_objects y cross join master.sys.all_objects x),
coinspad as (select * from @coins -- pad the parameter in case it has fewer than 8 rows.
union all select 1000000,0 union all select 1000001,0
union all select 1000002,0 union all select 1000003,0
union all select 1000004,0 union all select 1000005,0
union all select 1000006,0 union all select 1000007,0),
tempcoins as (select row_number() over (order by val) as seq, val, ccount from coinspad),
A1 as (select I*val as v from tempcoins, tally where seq=1 and I between 0 and ccount),
A2 as (select I*val as v from tempcoins, tally where seq=2 and I between 0 and ccount),
B2 as (select distinct A1.v+A2.v as v from A1 cross join A2),
A3 as (select I*val as v from tempcoins, tally where seq=3 and I between 0 and ccount),
B3 as (select distinct B2.v+A3.v as v from B2 cross join A3),
A4 as (select I*val as v from tempcoins, tally where seq=4 and I between 0 and ccount),
B4 as (select distinct B3.v+A4.v as v from B3 cross join A4),
A5 as (select I*val as v from tempcoins, tally where seq=5 and I between 0 and ccount),
B5 as (select distinct B4.v+A5.v as v from B4 cross join A5),
A6 as (select I*val as v from tempcoins, tally where seq=6 and I between 0 and ccount),
B6 as (select distinct B5.v+A6.v as v from B5 cross join A6),
A7 as (select I*val as v from tempcoins, tally where seq=7 and I between 0 and ccount),
B7 as (select distinct B6.v+A7.v as v from B6 cross join A7),
A8 as (select I*val as v from tempcoins, tally where seq=8 and I between 0 and ccount),
B8 as (select distinct B7.v+A8.v as v from B7 cross join A8)
select count(v) - 1 as answer from B8; -- subtracts one because using 0 coins is not allowed
go
-- examples of using it:-
declare @testlist play.coinlist;
select answer from play.coinlist @testlist; -- call it with no coins, it returns 0
insert @testlist(val,ccount) values(1,3),(2,2),(5,0),(10,3),(50,1);
select answer from play.coinlist @testlist; -- another simple one
delete @testlist; insert @testlist(val,ccount) values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35);
select answer from play.coinlist @testlist; -- a less simple one, with 8 rows in the parameter - the max allowed.
-- I picked 8 as my maximum number of denominations because that's how many are in general us in the UK
-- The UK coinage comes in units of 1,2,5,10,20,50,100 and 200 pence.
insert @testlist(val,ccount) values(500,99); -- push it up to 9 rows
select answer from play.coinlist @testlist; -- gives the wrong answer: only sees the first 8 rows in the table parameter.
-- the call above gives the same answer as the one before.
-- note: the UK has occassional special issues with coins which have a face value of 500 pence
-- but 500 pence coins are collectors pieces, generally more valuable than 500 pence, so are not used as money.
Tom
November 17, 2013 at 5:10 pm
Isn't that more a scenario for CROSS JOINS rather than a recursive cte?
I would use a Tally table to expand the number of coins per denomination and the CROSS JOIN to get the total amount.
But with the 5000 coins per denomination and 8 denomiations this would require "quite some data space" since we're talking about
390.625.000.000.000.000.000.000.000.000 possible solutions (including duplicates).
Just with 5 coins per denomination we already have 390625 possible solutions (5*5*5*5*5*5*5*5 = 5^8). Or am I missing something?
November 17, 2013 at 6:00 pm
Hi Tom,
A generic cte is possible, but I want to show you my WHILE loop first because it can handle the data and my CTE can't!
/* Combinations of coins - generic solution by Mister Magoo */
-- drop our temp tables if they exist
if object_id('tempdb..#values') is not null
drop table #values;
if object_id('tempdb..#coins') is not null
drop table #coins;
if object_id('tempdb..#results') is not null
drop table #results;
-- lets have a table for the coins - denomination and quantity
create table #coins(den smallint primary key not null,number int not null);
-- and some test data
insert #coins(den,number)
values(1,3),(2,2),(5,0),(10,3),(50,1); -- should come up with 63 values
/* some more test */
--values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35); -- should come up with 57596 values
--values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35),(500,99); -- should come up with 107096 values
-- let's build a tally cte
;with
E1(N) AS (
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
), --10E+1 or 10 rows
E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
E4(N) AS (SELECT 1 FROM E2 a, E2 b) --10E+4 or 10,000 rows max
/* you can add more elements to the cte to handle larger numbers of coins per denomination if required */
-- now generate all the possible values for each coin denomination
select den,den*n as value
into #values
from #coins coins
cross apply(
select 0
union all
select top (coins.number) row_number() over (order by (select null)) from e4
) ctetally(n);
-- index the list so we can get each denomination's values quickly
create clustered index ix_vals_ci on #values(den);
-- create somewhere to put the results
-- NOTE: the use of identity on "den" is to remove the need for an index
-- we can tell what we last processed by checking scope_identity()
create table #results(den int identity(1,1) not null , value int not null);
-- allow direct insertes of identity values
set identity_insert #results on;
-- add the first set of results for the first coin denomination
insert #results(den,value)
select den,value
from #values
where den = (Select min(den) from #values);
-- now a single statement while loop to insert the rest of the results
-- this works out as X inserts of sets of data where X = the number of coin denominations in the #coins table
-- this is the same logic as a recursive cte, but many times faster
while @@rowcount>0
insert #results(den,value)
-- use of distinct saves us processing duplicates as we go along
select distinct vals.den,base.value + vals.value
from
( -- let's get the last set of data we inserted from the #results table by using scope_identity() to identify them
select distinct value
from #results res
where res.den = scope_identity()
) base
cross join
( -- and cross join that with all the possible values of the next coin in the #coins table
select den,value
from #values vals
where vals.den = (
select top 1 coins.den
from #coins coins
where coins.den> scope_identity()
order by coins.den)
) vals;
-- finally the results, excluding zero
select distinct value
from #results
where value>0
order by value;
The rubbish CTE is here:
;with
coins(den,number) as
(
select den,number from (values(1,3),(2,2),(5,0),(10,3),(50,1))a(den,number)
),
E1(N) AS (
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
), --10E+1 or 10 rows
E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
E4(N) AS (SELECT 1 FROM E2 a, E2 b) --10E+4 or 10,000 rows max
, vals(den,value) as
(
select den,den*n
from coins
cross apply(
select 0
union all
select top (coins.number) row_number() over (order by (select null)) from e4
) ctetally(n)
), combinations as
(
select den,value
from vals
where den=(select min(den) from coins)
union all
select vals.den, vals.value + combi.value
from combinations as combi
cross apply ( select den,value
from (
select den,value,rank() over(order by den) as rnk
from vals
where vals.den>combi.den
) a
where a.rnk = 1
) vals
)
select distinct value
from combinations
where value>0
MM
select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);November 17, 2013 at 6:05 pm
I forgot to mention, the WHILE loop / *Identity Hack* version takes about the same time as your sample script for the 57596 result, and about 3 times that (30 seconds) for the 107096 result (with the £5 coin).
My generic CTE got cancelled on anything above the 63 result !
MM
select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);November 17, 2013 at 6:47 pm
Tom,
Interesting problem but I can't quite wrap my head around what you're looking for. But here's an rCTE solution that may be something like it.
CREATE TABLE #coinlist (val int, ccount int);
insert #coinlist(val,ccount) values(1,3),(2,2),(5,0),(10,3),(50,1);
WITH UniqueCoinCombos (n, Tuples, ID) AS
(
-- Return all possible combinations of the coins with cccount <> 0
SELECT 1, CAST(val AS VARCHAR(8000)), val
FROM #coinlist
WHERE ccount <> 0
UNION ALL
SELECT 1 + n.n, CAST(t.val AS VARCHAR(8000)) + ',' + n.Tuples, val
FROM UniqueCoinCombos n
CROSS APPLY (
SELECT val
FROM #coinlist t
WHERE t.val < n.ID) t
)
,Tally (n) AS
(
SELECT 0 UNION ALL
SELECT TOP 5000 ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM sys.all_columns a CROSS JOIN sys.all_columns b
)
-- Get the distinct number of unique sums
SELECT answer=COUNT(DISTINCT TotVal)
FROM
(
-- Sum the coin values within a unique combination
SELECT rn, n, TotVal=SUM(TotVal)
FROM
(
-- Split the delimited list (a combination of coin values)
-- and apply a Tally table to get 0 to ccount of each
SELECT rn, Item, d.n, TotVal=Item*d.n
FROM
(
-- Number each unique combination
SELECT *, rn=ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM UniqueCoinCombos
) a
CROSS APPLY DelimitedSplit8K(Tuples, ',') b
JOIN #coinlist c ON b.Item = c.val
CROSS APPLY
(
SELECT n
FROM Tally
WHERE n BETWEEN 0 AND c.ccount
) d
) a
GROUP BY rn, n
) a;
GO
DROP TABLE #coinlist;
This calculates the distinct set of sums for a coins group. The rCTE UniqueCoinCombos is an adaptation of the combinations (UNIQUEnTuples) rCTE noted here: http://www.sqlservercentral.com/Forums/FindPost1368129.aspx
Since this doesn't produce exactly the same answer yours does for the specified table, you may want to take a look at it and see where I misinterpreted what you're looking for.
My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.
Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St
November 23, 2013 at 8:31 am
LutzM (11/17/2013)
Isn't that more a scenario for CROSS JOINS rather than a recursive cte?
Yes, it needs cross joins if conditions that allow you to avod them aren't met. But how to do the right number of joins when you don't know how many joins there are when writing the query - that seems to be either looping or recursion. It's also necessary to do them in such a way as to avoid the combinatorial explosion.
The reason for picking 5000 when I started looking at this was to force that me to think about how to avoid that explosion, so probably I should have used a much lower number for my question here as it's not the issue I wanted help with, my problem was how to wrap suitable algorithms in a recursive or iterative framework in decent T-SQL - and for the cases where joins are the right way to go, demand driven dataflow seems sensible and that can only happen within a single query, so the decent framework is probably recursive not iterative.
I would use a Tally table to expand the number of coins per denomination and the CROSS JOIN to get the total amount.
But with the 5000 coins per denomination and 8 denomiations this would require "quite some data space" since we're talking about
390.625.000.000.000.000.000.000.000.000 possible solutions (including duplicates).
Just with 5 coins per denomination we already have 390625 possible solutions (5*5*5*5*5*5*5*5 = 5^8). Or am I missing something?
You've spotted the big combinatorial explosion issue. Early elimination of duplicates rather than doing an 8-way (actually 16-way) join and then eliminating duplicates makes a big difference. With 5000 each of 1,2,5,10,20,50 and 100 unit coins one can very easily reduce the number of rows generated to 8,801,725,001. That's a reduction by 19 or 20 decimal orders of magnitude in the number of rows (with 5 of each it would be 10,036 rows, not as spectacular an improvement but still quite a bit better than 390625) just by the trivial trick of eliminating duplicates once per join and throwing away the 0 value from the first generated set; the largest number of rows generated by an individual join in that process would be 4,900,940,000. That's without doing any clever algorithm design like detecting special cases and using different algorithms to fit different cases. For example in the case where each one coin value except the smallest can be made up from the available smaller coins one can avoid doing any joins other than the ones needed to check that the set of coins has property, which don't generate many rows, and that's going to be the most common case for large numbers of coins. There are 1,940,000 values other than 0 that can be generated from that set of 40,000 coins, and I wouldn't generate any rows at all to calculate that because there's enough of the smallest coin to generate the one coin value of any of the larger coins, so I didn't need to do any joins to see whether that coin set has the property that allows me to do arithmetic instead of generating and eliminating duplicates. For coin sets with large numbers of coins that don't have this property, there are often other algorithms based on weaker properties that shortcut the process not quite so much; for small numbers of coins one has to follow the join and eliminate duplicates track.
So my main interest in asking about this was how to build the thing so that the stages could be set up to do it properly for the cases where I do have to generate big sets and eliminate duplicates without having to alter the code when the number of possible coin values changes.
Tom
November 23, 2013 at 10:51 am
mister.magoo (11/17/2013)
Hi Tom,A generic cte is possible, but I want to show you my WHILE loop first because it can handle the data and my CTE can't!
I'm beginning to think that a recursive CTE probably isn't the right approach after all. But I'm not at all sure either way.
/* Combinations of coins - generic solution by Mister Magoo */
-- drop our temp tables if they exist
if object_id('tempdb..#values') is not null
drop table #values;
if object_id('tempdb..#coins') is not null
drop table #coins;
if object_id('tempdb..#results') is not null
drop table #results;
-- lets have a table for the coins - denomination and quantity
create table #coins(den smallint primary key not null,number int not null);
-- and some test data
insert #coins(den,number)
values(1,3),(2,2),(5,0),(10,3),(50,1); -- should come up with 63 values
/* some more test */
--values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35); -- should come up with 57596 values
--values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35),(500,99); -- should come up with 107096 values
-- let's build a tally cte
;with
E1(N) AS (
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
), --10E+1 or 10 rows
E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
E4(N) AS (SELECT 1 FROM E2 a, E2 b) --10E+4 or 10,000 rows max
/* you can add more elements to the cte to handle larger numbers of coins per denomination if required */
-- now generate all the possible values for each coin denomination
select den,den*n as value
into #values
from #coins coins
cross apply(
select 0
union all
select top (coins.number) row_number() over (order by (select null)) from e4
) ctetally(n);
-- index the list so we can get each denomination's values quickly
create clustered index ix_vals_ci on #values(den);
-- create somewhere to put the results
-- NOTE: the use of identity on "den" is to remove the need for an index
-- we can tell what we last processed by checking scope_identity()
create table #results(den int identity(1,1) not null , value int not null);
-- allow direct insertes of identity values
set identity_insert #results on;
-- add the first set of results for the first coin denomination
insert #results(den,value)
select den,value
from #values
where den = (Select min(den) from #values);
-- now a single statement while loop to insert the rest of the results
-- this works out as X inserts of sets of data where X = the number of coin denominations in the #coins table
-- this is the same logic as a recursive cte, but many times faster
while @@rowcount>0
insert #results(den,value)
-- use of distinct saves us processing duplicates as we go along
select distinct vals.den,base.value + vals.value
from
( -- let's get the last set of data we inserted from the #results table by using scope_identity() to identify them
select distinct value
from #results res
where res.den = scope_identity()
) base
cross join
( -- and cross join that with all the possible values of the next coin in the #coins table
select den,value
from #values vals
where vals.den = (
select top 1 coins.den
from #coins coins
where coins.den> scope_identity()
order by coins.den)
) vals;
-- finally the results, excluding zero
select distinct value
from #results
where value>0
order by value;
That's quite a lot faster than my single query non-generic version made to be a TV UDF when I run it on my machine.
I wondered why, so I played with my code a little:
I took away the UDF wrapping, rejigged the seven two-component steps as seven single-component steps, changed it to use a temp table instead of a table variable, and used my permanent Tally table (which has an index) instead of creating one on the fly. That gave me an 8 times speedup - the result is quite a lot faster than your loop; but your loop will handle any number of denominations, my single query (now as a freestanding select with several CTEs, not a UDF) will only handle 8. I think that having to put the increments into a table in order to allow an effectively unlimited variable number of denominations while still being able to discard duplicates on the fly instead of at the end costs performance, so that there is a clear performance-flexibility trade-off there. It's also pretty clear that for this sort of thing a UDF with a table variable parameter doesn't cut it, even if it's a single statement table-valued UDF. I also think that writing the seven three-way joins as two stages each was a mistake (stupid of me to have done that).
Tom
November 23, 2013 at 12:24 pm
mister.magoo (11/17/2013)
I forgot to mention, the WHILE loop / *Identity Hack* version takes about the same time as your sample script for the 57596 result, and about 3 times that (30 seconds) for the 107096 result (with the £5 coin).
That's odd. On my machine your loop is a lot faster than my sample script.
My generic CTE got cancelled on anything above the 63 result !
Yes, well the run time will be roughly proportionate to the product of all the non-zero numbers of coins, because it computes the whole product before starting duplicate elimination so you would probably cancel it after a while if that product were about 100,000,000, which is what it would be on the 57596 answer. For the 63 answer the product is 18. If that ran in a milisecond the 57596 answer would take about 3 days to reach. I measured it's run-time on a set of coinsets to see whether perhaps an on-demand execution order (something like lazy evaluation) was ameliorating that, and the results were that the execution time was indeed roughly proportional to that product. There was a fair bit of scatter, but it looked as if the best fit was linear; and I didn't measure anything that lasted longer than 5 mins, so it may curve down later.
The problem I'm having with making a generic CTE soluton is that every time I try to make it do some pruning early instead of leaving it all to the end, or test for a case where I can do something else instead of a full set of crossjoins, I find I'm breaking the rules - doing things not allowed in a recursive CTE, or wanting to do someting which just isn't allowed in SQL. Actually SQL (and T-SQL) has very poor expressive capability compared to other languages because it's in many ways a low level language - you can't for example have a case expression which delivers a table in the FROM clause of a select, because row sets or tables are not first class objects in the language. Neither are rows. It's a real pain to write in a language where the main entitities are not first class objects.
Tom
November 23, 2013 at 1:45 pm
dwain.c (11/17/2013)
Tom,Interesting problem but I can't quite wrap my head around what you're looking for. But here's an rCTE solution that may be something like it.
<code omitted>
This calculates the distinct set of sums for a coins group. The rCTE UniqueCoinCombos is an adaptation of the combinations (UNIQUEnTuples) rCTE noted here: http://www.sqlservercentral.com/Forums/FindPost1368129.aspx
Since this doesn't produce exactly the same answer yours does for the specified table, you may want to take a look at it and see where I misinterpreted what you're looking for.
Hi Dwain,
Thanks for that. I like the way you build tuples and then use them, and I'll see where that takes me. Sorry it's taken so long to reply - I've had a bit of a hectic week.
The comments on your code suggest that you interpreted me correctly, but
unfortunately the code doesn't get all the distinct set of sums mentioned above: it leaves some out. The problem is in this block of code:
SELECT rn, n, TotVal=SUM(TotVal)
FROM
(
-- Split the delimited list (a combination of coin values)
-- and apply a Tally table to get 0 to ccount of each
SELECT rn, Item, d.n, TotVal=Item*d.n
FROM
(
-- Number each unique combination
SELECT *, rn=ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM UniqueCoinCombos
) a
CROSS APPLY DelimitedSplit8K(Tuples, ',') b
JOIN #coinlist c ON b.Item = c.val
CROSS APPLY
(
SELECT n
FROM Tally
WHERE n BETWEEN 0 AND c.ccount
) d
) a
GROUP BY rn, n
The problem is that for each value of n only 1 combination will be considered for that value of n; the combination in which every denomination listed in the tuple and allowed at least that many coins has n coins and every other denomination has none. So any combination in which two coins occur in different nonzero numbers is omitted. For example if the starting point is very simple - up to 1 one cent coin and up to 2 ten cent coins are allowed and nothing else the only combinations that will be noted for the uple 0,1 are
no coins at all (n=0) total 0 cents
one one cent coin and one ten cent coin (n=1) total 11 cents
no one cent coins and two ten cent coins (n=2) total 20 cents
The combination one on cent coin and two ten cent coins, total 21 cents, is not counted because the two coins would be present in different quantities. So the count would be reported as 4 (1,10,11 and 20) but is actually 5 (1,10,11,20 and 21).
I checked this by running an example:
I ran with values(1,1),(2,2),(10,1) in coins to see what would happen, with the code modified display the result of the select above instead of the final result, with each row labelled by the tuple that generated it, because I was sure the error lay there. The tuple 1,2,10 got only 3 rows, with Totval values 0, 13 and 10, so 15, which was possible for this tuple and only for this tuple, was missing. Also the tuple 2,10 got only 0, 12 and 4 so 14 was showing up for neither of the two tuples that could generate it. This meant that the number of distinct sums reported would be 2 less than the actual number of distinct sums possible.
The idea of building tuples and then using a splitter to pull them apart looks promising. I am going to have a look and see if I gets me where I want to be, ie in a position to do early pruning for the case where all the joins are necessary because none of the conditions for alternative algorithms are satisfied without losing the ability to cope with a fairly unlimited variable number of denominations. I think I will have to either invent some rules such as no two denominations may be coprime and no denomination can be more than 500 times the smallest denomination, or have a much smaller limits on number of coins, though.
Tom
November 24, 2013 at 7:40 pm
Edit: cold light of day made me realize I had posted flawed code...
MM
select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);November 25, 2013 at 12:14 am
L' Eomot Inversé (11/23/2013)
The idea of building tuples and then using a splitter to pull them apart looks promising. I am going to have a look and see if I gets me where I want to be, ie in a position to do early pruning for the case where all the joins are necessary because none of the conditions for alternative algorithms are satisfied without losing the ability to cope with a fairly unlimited variable number of denominations. I think I will have to either invent some rules such as no two denominations may be coprime and no denomination can be more than 500 times the smallest denomination, or have a much smaller limits on number of coins, though.
Tom - Your analysis was spot on. I couldn't make it work using the approach I tried.
Looks to me like you've already done a pretty dynamite job with your cascading CTEs. Didn't look in detail at what MM posted above, but yours smokes anything I was able to come up with.
Nice one!
My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.
Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St
Viewing 11 posts - 1 through 10 (of 10 total)
You must be logged in to reply to this topic. Login to reply