# Combinations question with a twist

• Hi all,
Consider the data below, I need every combination that totals 130.
So, 130, 55 + 75; 65 + 55 + 10, etc...
Yes  I am aware there are dupes: each val represents a separate collection of items.

Any  help on this would be appreciated. I've poked around, but not found the SUM(nval) = 130, nor a way of handling up to 500 rows in the table.
The  SUM(nVal) could be up to 1000.

Thanks!

`DECLARE @t TABLE (nId INTEGER IDENTITY,  nVal INTEGER)INSERT @t (nVal) VALUES (130)INSERT @t (nVal) VALUES (124)INSERT @t (nVal) VALUES (123)INSERT @t (nVal) VALUES (122)INSERT @t (nVal) VALUES (121)INSERT @t (nVal) VALUES (120)INSERT @t (nVal) VALUES (116)INSERT @t (nVal) VALUES (116)INSERT @t (nVal) VALUES (115)INSERT @t (nVal) VALUES (112)INSERT @t (nVal) VALUES (108)INSERT @t (nVal) VALUES (75)INSERT @t (nVal) VALUES (75)INSERT @t (nVal) VALUES (74)INSERT @t (nVal) VALUES (72)INSERT @t (nVal) VALUES (71)INSERT @t (nVal) VALUES (65)INSERT @t (nVal) VALUES (65)INSERT @t (nVal) VALUES (64)INSERT @t (nVal) VALUES (59)INSERT @t (nVal) VALUES (58)INSERT @t (nVal) VALUES (57)INSERT @t (nVal) VALUES (56)INSERT @t (nVal) VALUES (55)INSERT @t (nVal) VALUES (55)INSERT @t (nVal) VALUES (48)INSERT @t (nVal) VALUES (41)INSERT @t (nVal) VALUES (31)INSERT @t (nVal) VALUES (27)INSERT @t (nVal) VALUES (23)INSERT @t (nVal) VALUES (22)INSERT @t (nVal) VALUES (21)INSERT @t (nVal) VALUES (20)INSERT @t (nVal) VALUES (18)INSERT @t (nVal) VALUES (18)INSERT @t (nVal) VALUES (17)INSERT @t (nVal) VALUES (17)INSERT @t (nVal) VALUES (16)INSERT @t (nVal) VALUES (15)INSERT @t (nVal) VALUES (14)INSERT @t (nVal) VALUES (14)INSERT @t (nVal) VALUES (14)INSERT @t (nVal) VALUES (14)INSERT @t (nVal) VALUES (13)INSERT @t (nVal) VALUES (12)INSERT @t (nVal) VALUES (11)INSERT @t (nVal) VALUES (10)INSERT @t (nVal) VALUES (9)INSERT @t (nVal) VALUES (9)INSERT @t (nVal) VALUES (9)INSERT @t (nVal) VALUES (8)INSERT @t (nVal) VALUES (7)INSERT @t (nVal) VALUES (7)INSERT @t (nVal) VALUES (7)INSERT @t (nVal) VALUES (6)INSERT @t (nVal) VALUES (6)`

• I'm not really sure that SQL server is going to be the right answer for this. I assume that you can use an unlimited amount of the numbers, so in your example you have 55 + 75 = 55 + 65 +10 = 130. Is, also, the equation 6 + 6 + 7 + 7 + 7 + 8 + 9 + 9 + 9+ 10 + 11 + 12 + 13 + 16 valid? Can the reverse of an equation also be used as well. So 6 + 124 could be used twice (as you have two 6's), but you could also have 124 + 6 twice? Or is 124 + 6 invalidated by the prior use of 6 + 124?

Someone might have a solution out there, but I'm not necessarily sure it'll be efficient.

Thom~

Excuse my typos and sometimes awful grammar. My fingers work faster than my brain does.
Larnu.uk

• You've posted in the SQL Server 2008 forum.  Is that actually what you're using?

John

• Yep.

• schleep - Friday, August 11, 2017 5:08 AM

Yep.

"Yep"? There have been several questions asked before your post. Which one(s) are you answer(ing)?

Thom~

Excuse my typos and sometimes awful grammar. My fingers work faster than my brain does.
Larnu.uk

• Ah sorry. Yes, SQL 2008

I'm not really sure that SQL server is going to be the right answer for this. I assume that you can use an unlimited amount of the numbers, so in your example you have 55 + 75 = 55 + 65 +10 = 130. Is, also, the equation 6 + 6 + 7 + 7 + 7 + 8 + 9 + 9 + 9+ 10 + 11 + 12 + 13 + 16 valid?

Yes, any combination is valid.

Can the reverse of an equation also be used as well. So 6 + 124 could be used twice (as you have two 6's), but you could also have 124 + 6 twice? Or is 124 + 6 invalidated by the prior use of 6 + 124?

Yes there are 2 distinct :hehe: 6s, so either of the 2 combinations of 6 and 124 will work. Don't need the permutations (124 + 6)

To be clearer, let's say there are 130 cities in a given province/state. The goal is to ensure that all cities are covered. In my case, I discovered that we had the wrong 6 with the 124 (there was overlap in the sets, and several cities were not covered. So I fearlessly opened that can'o'worms, and here we are🙂

• "Are all cities covered" is a much simpler question to answer than giving you all possible combinations of values.  I did write a recursive CTE to answer this question, but killed it after an hour when it had reached over 300,000 combinations.  (And I only included combinations in descending order.)

Drew

J. Drew Allen

• with the 56 rows in your sample data...to cover all possible combinations will generate 72 057 594 037 927 935 rows  (2^(56) -1) ....:w00t::w00t:

________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day

• I know.:crying: BIGINT can handle the 56 case. But we have 237 groups in on province.

Let me rephrase: my users have created various groupings of cities within provinces/states. The rule is that all cities must be covered by some combination of these groups.
In one case, 50!!! groups are used to cover a province.

So, is  there another way to go about this? My goal was to identify the groups that could possibly fit in those cases where there is missing cover?
Or is this a case where I give the users a report of missing cover, declare victory, retreat, and let them deal with it?

• my users have created various groupings of cities within provinces/states. The rule is that all cities must be covered by some combination of these groups

can you give some sample set up data that explains this and your expected results of the sample data

________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day

• can you give some sample set up data that explains this and your expected results of the sample data

Not easily with a real-world example, I'm afraid.
I'm leaving the office shortly, I'll think on it over the weekend (no internet), and I may be able to gerry-rig a small-scale example with test data next week.

• schleep - Friday, August 11, 2017 8:45 AM

can you give some sample set up data that explains this and your expected results of the sample data

Not easily with a real-world example, I'm afraid.
I'm leaving the office shortly, I'll think on it over the weekend (no internet), and I may be able to gerry-rig a small-scale example with test data next week.

just a thought

`USE [tempdb]GO`

`CREATE TABLE [dbo].[all_provinces](    [province] [varchar](2) NOT NULL) `

`CREATE TABLE [dbo].[grp_province](    [grp] [int] NOT NULL,    [province] [varchar](2) NOT NULL) INSERT [dbo].[all_provinces] ([province]) VALUES (N'A')INSERT [dbo].[all_provinces] ([province]) VALUES (N'B')INSERT [dbo].[all_provinces] ([province]) VALUES (N'C')INSERT [dbo].[all_provinces] ([province]) VALUES (N'D')INSERT [dbo].[all_provinces] ([province]) VALUES (N'E')INSERT [dbo].[all_provinces] ([province]) VALUES (N'F')INSERT [dbo].[all_provinces] ([province]) VALUES (N'G')INSERT [dbo].[all_provinces] ([province]) VALUES (N'H')INSERT [dbo].[all_provinces] ([province]) VALUES (N'I')INSERT [dbo].[all_provinces] ([province]) VALUES (N'J')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (1, N'A')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (1, N'B')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (1, N'J')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (2, N'B')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (2, N'C')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (2, N'I')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (3, N'C')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (3, N'H')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (3, N'G')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (3, N'D')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (4, N'J')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (4, N'I')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (4, N'H')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (5, N'F')INSERT [dbo].[grp_province] ([grp], [province]) VALUES (5, N'G')`

`SELECT provinceFROM all_provincesEXCEPTSELECT DISTINCT   provinceFROM grp_provinceORDER BY province;`

________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day

• This problem has a massive search space. SQL server won't be the fastest solution. Instead of using a table variable you should use a temporary table. It can be done with a recursive common table expression, but this won't be the fastest method. I had a quick go with the SQL below on the table variable you create.
`DECLARE @Total int = 130;WITH cte AS(  SELECT 1 Level,    x.nId,    nval,    nval Total,    CONVERT(nvarchar(1000),x.nId) Ids  FROM @t x   WHERE x.nVal <= @Total  UNION all  SELECT x.Level + 1  AS Level,    y.nId    AS nId,    y.nval   AS nval,    x.Total+y.nVal AS Total,    CONVERT(nvarchar(1000),CONCAT(x.Ids,',', y.nId))  FROM cte x  INNER join @t y      on y.nId > x.nId   WHERE x.nval+y.nVal <= @Total   AND x.Level < 6)SELECT count(* ) FROM cte WHERE Total = @Total`
You can increase the criteria on Level above 6 but it will take longer (a lot longer).
It took 80 seconds on my machine to get 55,492 combination of nId

• If you use a temporary table you should get better performance:
`IF OBJECT_ID('tempdb..#t','U') IS NOT NULL  DROP TABLE #tCREATE TABLE #t (nId INTEGER IDENTITY, nVal INTEGER)CREATE CLUSTERED INDEX IX_#t_1 ON #t(nId,nVal)INSERT #t (nVal) VALUES (130)INSERT #t (nVal) VALUES (124)...`
The following SQL went 13 levels deep in 81 seconds on my machine and produced all (3,104,310) results that total to 130
`SET NOCOUNT ON`

`IF OBJECT_ID('tempdb..#t','U') IS NOT NULL DROP TABLE #tCREATE TABLE #t (nId smallint IDENTITY, nVal smallint)CREATE CLUSTERED INDEX IX_#t_1 ON #t(nId,nVal)`

`INSERT #t (nVal) VALUES (130)INSERT #t (nVal) VALUES (124)INSERT #t (nVal) VALUES (123)INSERT #t (nVal) VALUES (122)INSERT #t (nVal) VALUES (121)INSERT #t (nVal) VALUES (120)INSERT #t (nVal) VALUES (116)INSERT #t (nVal) VALUES (116)INSERT #t (nVal) VALUES (115)INSERT #t (nVal) VALUES (112)INSERT #t (nVal) VALUES (108)INSERT #t (nVal) VALUES (75)INSERT #t (nVal) VALUES (75)INSERT #t (nVal) VALUES (74)INSERT #t (nVal) VALUES (72)INSERT #t (nVal) VALUES (71)INSERT #t (nVal) VALUES (65)INSERT #t (nVal) VALUES (65)INSERT #t (nVal) VALUES (64)INSERT #t (nVal) VALUES (59)INSERT #t (nVal) VALUES (58)INSERT #t (nVal) VALUES (57)INSERT #t (nVal) VALUES (56)INSERT #t (nVal) VALUES (55)INSERT #t (nVal) VALUES (55)INSERT #t (nVal) VALUES (48)INSERT #t (nVal) VALUES (41)INSERT #t (nVal) VALUES (31)INSERT #t (nVal) VALUES (27)INSERT #t (nVal) VALUES (23)INSERT #t (nVal) VALUES (22)INSERT #t (nVal) VALUES (21)INSERT #t (nVal) VALUES (20)INSERT #t (nVal) VALUES (18)INSERT #t (nVal) VALUES (18)INSERT #t (nVal) VALUES (17)INSERT #t (nVal) VALUES (17)INSERT #t (nVal) VALUES (16)INSERT #t (nVal) VALUES (15)INSERT #t (nVal) VALUES (14)INSERT #t (nVal) VALUES (14)INSERT #t (nVal) VALUES (14)INSERT #t (nVal) VALUES (14)INSERT #t (nVal) VALUES (13)INSERT #t (nVal) VALUES (12)INSERT #t (nVal) VALUES (11)INSERT #t (nVal) VALUES (10)INSERT #t (nVal) VALUES (9)INSERT #t (nVal) VALUES (9)INSERT #t (nVal) VALUES (9)INSERT #t (nVal) VALUES (8)INSERT #t (nVal) VALUES (7)INSERT #t (nVal) VALUES (7)INSERT #t (nVal) VALUES (7)INSERT #t (nVal) VALUES (6)INSERT #t (nVal) VALUES (6)`

`IF OBJECT_ID(N'tempdb..#Results','U') IS NOT NULL DROP TABLE #ResultsCREATE TABLE #Results (Iteration smallint, nId smallint, Total smallint,Ids varchar(500),SumExpression nvarchar(1000))CREATE CLUSTERED INDEX IX_#Results_1 ON #Results (Iteration,nId,Total)`

`DECLARE @Total int = 130`

`INSERT INTO #Results ( Iteration, nId, Total, Ids, SumExpression)SELECT 0,   x.nId,   x.nVal,   x.nId,   x.nVal FROM #t x ORDER BY x.nId`

`DECLARE @n smallint = 0DECLARE @RowCount int = -1 -- Set to a value that will allow it into the while loopWHILE @RowCount <> 0 BEGIN  INSERT INTO #Results  (  Iteration,  nId,  Total,  Ids,  SumExpression  )  SELECT @n+1,    x.nId,    x.nVal + r.Total,    CONCAT(r.Ids ,',',x.nId),    CONCAT(r.SumExpression ,'+',x.nVal)  FROM #Results r   INNER JOIN #t x      ON x.nId > r.nId    AND x.nVal + r.Total <= @Total  WHERE r.Iteration = @n`

` SET @RowCount = @@ROWCOUNT PRINT CONCAT('Iteration:',@n,'Inserted:',@RowCount) SET @n = @n + 1`

`ENDSELECT * FROM #Results r WHERE r.Total = @TotalORDER BY SumExpression `

• Thank you all for having a go at this.

I don't see any  realistic way to get around this in a timely manner, and can't really justify spending anymore time on it.
So I'm just going to create a report for the users pointing out those cases where the coverage is incomplete, and be done with this.

Thanks again.

Viewing 15 posts - 1 through 14 (of 14 total)

You must be logged in to reply to this topic. Login to reply