

SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 10:06 PM
Points: 8,283,
Visits: 8,733


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 nonempty 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 tablevalued 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




SSCertifiable
Group: General Forum Members
Last Login: Tuesday, April 01, 2014 9:38 AM
Points: 6,908,
Visits: 12,624


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?
Lutz A pessimist is an optimist with experience.
How to get fast answers to your question How to post performance related questions Links for Tally Table , Cross Tabs and Dynamic Cross Tabs , Delimited Split Function




SSCommitted
Group: General Forum Members
Last Login: Yesterday @ 8:01 AM
Points: 1,651,
Visits: 5,201


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
MMGrid AddinMMNose Addin
Forum Etiquette: How to post Reporting Services problemsForum Etiquette: How to post data/code on a forum to get the best help  by Jeff ModenHow to Post Performance Problems  by Gail Shaw




SSCommitted
Group: General Forum Members
Last Login: Yesterday @ 8:01 AM
Points: 1,651,
Visits: 5,201





Hall of Fame
Group: General Forum Members
Last Login: Yesterday @ 6:03 PM
Points: 3,590,
Visits: 5,098


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 mantra: No loops! No CURSORs! No RBAR! Hoouh!
My thought question: Have you ever been told that your query runs too fast?
My advice: INDEXing a poorperforming 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? Since random numbers are too important to be left to chance, let's generate some! Learn to understand recursive CTEs by example. Splitting strings based on patterns can be fast!




SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 10:06 PM
Points: 8,283,
Visits: 8,733


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 TSQL  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 8way (actually 16way) 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




SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 10:06 PM
Points: 8,283,
Visits: 8,733


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 nongeneric 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 twocomponent steps as seven singlecomponent 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 performanceflexibility tradeoff 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 tablevalued UDF. I also think that writing the seven threeway joins as two stages each was a mistake (stupid of me to have done that).
Tom




SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 10:06 PM
Points: 8,283,
Visits: 8,733


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 nonzero 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 runtime on a set of coinsets to see whether perhaps an ondemand 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 TSQL) 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




SSCrazy Eights
Group: General Forum Members
Last Login: Yesterday @ 10:06 PM
Points: 8,283,
Visits: 8,733


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.aspxSince 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




SSCommitted
Group: General Forum Members
Last Login: Yesterday @ 8:01 AM
Points: 1,651,
Visits: 5,201




