August 10, 2017 at 12:00 pm
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)
August 11, 2017 at 3:36 am
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
August 11, 2017 at 4:29 am
You've posted in the SQL Server 2008 forum. Is that actually what you're using?
John
August 11, 2017 at 5:08 am
Yep.
August 11, 2017 at 5:29 am
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🙂
August 11, 2017 at 7:09 am
"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
Business Intelligence Analyst
Philadelphia, PA
August 11, 2017 at 7:33 am
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
August 11, 2017 at 8:26 am
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?
August 11, 2017 at 8:33 am
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
August 11, 2017 at 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.
August 11, 2017 at 8:56 am
schleep - Friday, August 11, 2017 8:45 AMcan 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 province
FROM all_provinces
EXCEPT
SELECT DISTINCT
province
FROM grp_province
ORDER BY province;
________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day
August 11, 2017 at 9:19 am
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
August 11, 2017 at 9:38 am
If you use a temporary table you should get better performance:IF OBJECT_ID('tempdb..#t','U') IS NOT NULL
DROP TABLE #t
CREATE 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 130SET NOCOUNT ON
IF OBJECT_ID('tempdb..#t','U') IS NOT NULL
DROP TABLE #t
CREATE 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 #Results
CREATE 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 = 0
DECLARE @RowCount int = -1 -- Set to a value that will allow it into the while loop
WHILE @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
END
SELECT *
FROM #Results r
WHERE r.Total = @Total
ORDER BY SumExpression
August 14, 2017 at 6:42 am
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