| Author |
Topic  |
|
|
pelegk2
Aged Yak Warrior
Israel
723 Posts |
Posted - 01/24/2007 : 04:42:53
|
i am looking for an algoritem for this : i have table id's and numbers where and id can appear more then once foer example : id number 33 55 6541 42 33 99 33 58.3
and i want to find all the rows that have id=33 and the sum (number)+10<=GIVEN VALUE which means : the sum of the numbers of id=33 can have a DELTA of up to 10 when comparing to a given number! which means : sum (number)<= GIVEN VALUE<=sum (number)+10 how can i build a smart algoritem for that? thnaks i nadvance peleg
Israel -the best place to live in aftr heaven 9but no one wan't to go there so fast -:) |
|
|
khtan
In (Som, Ni, Yak)
Singapore
16769 Posts |
Posted - 01/24/2007 : 04:52:27
|
select id
from tbl
group by id
having sum(number) <= @given_value + 10
and sum(number) >= @given_value - 10
KH
|
 |
|
|
pelegk2
Aged Yak Warrior
Israel
723 Posts |
Posted - 01/24/2007 : 05:57:56
|
ok a little more complicated : i have table with : id,number,uniqueid and i want to know which of the rows should i take if i want to get the exact sum(number)=120 wehere : id number uniqueid 33 55 xde3 65 41 fed3 33 40 65f3e 33 58.3 df54 33 40 fE2c 33 20 lbcE 33 20 Wqazx 33 40 Lgco#z in this case there are at least 2 ways to get the sum of 120 how can i make a query that will return at least 1 case with all the relevent rows of sum(number)=120, and only if this case dosent exist i will check in the range as before sum (number)<= GIVEN VALUE<=sum (number)+10 and will get back the list of relevent rows! thnaks in advance peleg
Israel -the best place to live in aftr heaven 9but no one wan't to go there so fast -:) |
 |
|
|
khtan
In (Som, Ni, Yak)
Singapore
16769 Posts |
Posted - 01/24/2007 : 06:16:19
|
Now this is getting interesting. Peter where are you ? 
peleg, so it can be any combination as long as the sum is 120 ? Does it has to be same id ?
KH
|
 |
|
|
pelegk2
Aged Yak Warrior
Israel
723 Posts |
Posted - 01/24/2007 : 06:20:31
|
yes it must be on the same id and any combination as long as i get 120 for example
Israel -the best place to live in aftr heaven 9but no one wan't to go there so fast -:) |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/24/2007 : 06:53:12
|
How many records are there at MOST for each and one "id-group"? How many distinct values are there at MOST for a Number?
Peter Larsson Helsingborg, Sweden |
Edited by - SwePeso on 01/24/2007 06:55:32 |
 |
|
|
pelegk2
Aged Yak Warrior
Israel
723 Posts |
Posted - 01/24/2007 : 08:08:34
|
the can be even up to 100000 for each and one "id-group".
"How many distinct values are there at MOST for a Number"? can be mabye tops 200-300 tops
Israel -the best place to live in aftr heaven 9but no one wan't to go there so fast -:) |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/24/2007 : 17:49:59
|
First of all, create this function.CREATE FUNCTION dbo.fnGetAnyCombination
(
@WantedSum MONEY
)
RETURNS @Data TABLE (UniqueID VARCHAR(12) PRIMARY KEY, Number MONEY)
AS
BEGIN
-- Stage the data
DECLARE @Stage TABLE (RowID INT IDENTITY(0, 1), Number MONEY, UniqueID VARCHAR(12))
INSERT @Stage
(
Number,
UniqueID
)
SELECT Number,
UniqueID
FROM [Sample]
-- Create the control mechanism
DECLARE @Control TABLE (Bit SMALLINT IDENTITY(0, 1) PRIMARY KEY, Value TINYINT)
DECLARE @Value TINYINT,
@Mem TINYINT,
@Items INT
SELECT @Items = COUNT(*),
@Mem = 1
FROM @Stage
INSERT @Control
(
Value
)
SELECT 1
WHILE @Mem < @Items
BEGIN
INSERT @Control
(
Value
)
SELECT 0
SELECT @Mem = @Mem + 1
END
-- Work with the data
WHILE EXISTS (SELECT NULL FROM @Control WHERE Value = 1)
BEGIN
INSERT @Data
(
UniqueID,
Number
)
SELECT s.UniqueID,
s.Number
FROM @Stage AS s
INNER JOIN @Control AS c ON c.Bit = s.RowID
WHERE c.Value = 1
IF (SELECT SUM(Number) FROM @Data) = @WantedSum
BREAK
ELSE
DELETE
FROM @Data
SELECT @Mem = 1
UPDATE @Control
SET @Value = CASE WHEN Value + @Mem = 1 THEN 1 ELSE 0 END,
@Mem = CASE WHEN Value + @Mem = 2 THEN 1 ELSE 0 END,
Value = @Value
END
RETURN
END And then simply write this test application.-- Prepare sample data
CREATE TABLE [Sample]
(
UniqueID VARCHAR(12),
Number MONEY,
)
INSERT [Sample]
SELECT 'a', -10 UNION ALL
SELECT 'b', 40 UNION ALL
SELECT 'c', 10 UNION ALL
SELECT 'd', -20 UNION ALL
SELECT 'e', 10 UNION ALL
SELECT 'f', 40
-- Show some results
SELECT -30, * FROM dbo.fnGetAnyCombination(-30)
SELECT -20, * FROM dbo.fnGetAnyCombination(-20)
SELECT -10, * FROM dbo.fnGetAnyCombination(-10)
SELECT 0, * FROM dbo.fnGetAnyCombination(0)
SELECT 10, * FROM dbo.fnGetAnyCombination(10)
SELECT 20, * FROM dbo.fnGetAnyCombination(20)
SELECT 30, * FROM dbo.fnGetAnyCombination(30)
SELECT 40, * FROM dbo.fnGetAnyCombination(40)
SELECT 50, * FROM dbo.fnGetAnyCombination(50)
SELECT 60, * FROM dbo.fnGetAnyCombination(60)
SELECT 70, * FROM dbo.fnGetAnyCombination(70)
SELECT 80, * FROM dbo.fnGetAnyCombination(80)
SELECT 90, * FROM dbo.fnGetAnyCombination(90)
SELECT 100, * FROM dbo.fnGetAnyCombination(100)
DROP TABLE [Sample] Peter Larsson Helsingborg, Sweden |
Edited by - SwePeso on 01/24/2007 17:57:35 |
 |
|
|
khtan
In (Som, Ni, Yak)
Singapore
16769 Posts |
Posted - 01/24/2007 : 19:58:55
|
Excellent work Peter 
KH
|
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/25/2007 : 00:55:41
|
Thanks. It took some thinking for converting my normal horizontal binary counter to a vertical equivalent.
Enjoy!
Peter Larsson Helsingborg, Sweden |
Edited by - SwePeso on 01/25/2007 01:03:42 |
 |
|
|
pelegk2
Aged Yak Warrior
Israel
723 Posts |
Posted - 01/25/2007 : 03:48:30
|
nice work !!!! Q : why did u you a table of type (@) and not of type (#) ???? for faster performance? thnaks in advance peleg
Israel -the best place to live in aftr heaven 9but no one wan't to go there so fast -:) |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/25/2007 : 04:24:36
|
Easier to run when debugging since table variables are highly volatile and are "dropped" when out ot scope or current run is ended.
Peter Larsson Helsingborg, Sweden |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/25/2007 : 04:28:30
|
If you rewrite the code above as SP, you can use # for table prefix, because that is not allowed in function. Functions are more versatile in this case, because you can include them in a query
select *, case when exists (select * from dbo.fnGetAnyCombination(25)) then 'do this' else 'do that' end from yourtable
Peter Larsson Helsingborg, Sweden |
 |
|
|
pelegk2
Aged Yak Warrior
Israel
723 Posts |
Posted - 01/25/2007 : 13:11:20
|
ok thnaks alot for all the info
Israel -the best place to live in aftr heaven 9but no one wan't to go there so fast -:) |
 |
|
|
rockmoose
SQL Natt Alfen
Sweden
3279 Posts |
Posted - 01/25/2007 : 20:18:46
|
Good!
This can also be done with recursive CTE in sql2005... (gets all matches, not only first match)
create table test(id int, number money, uniqueid varchar(10) primary key)
insert test
select 33, 55, 'xde3'
union all select 65, 41, 'fed3'
union all select 33, 40, '65f3e'
union all select 33, 58.3, 'df54'
union all select 33, 40, 'fE2c'
union all select 33, 20, 'lbcE'
union all select 33, 20, 'Wqazx'
union all select 33, 40, 'Lgco#z'
-- pick the id we want to investigate
declare @id int; set @id = 33
;with cte(uniqueid,numberSum)
as
(
select cast(uniqueid as varchar(max)),number
from test
where id = @id
union all
-- note the delimiting character ',' must not exist in the uniqueid column!!! but you can choose any character
select a.uniqueid+','+b.uniqueid, a.numberSum+b.number
from cte a join test b
on case when charindex(',',a.uniqueid) = 0
then a.uniqueid
else right(a.uniqueid,charindex(',',reverse(a.uniqueid))-1)
end < b.UniqueID
and b.id = @id
)
select @id as id,*
from cte
where numberSum = 98.3
--numberSum between 30 and 50
-- drop table test
id uniqueid numberSum
----------- ------------------------------------ ---------------------
33 df54,fE2c 98.3000
33 df54,Lgco#z 98.3000
33 df54,lbcE,Wqazx 98.3000
33 65f3e,df54 98.3000
rockmoose |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/26/2007 : 02:38:05
|
How many recursive calls does SQL Server 2005 accept?
Here is my original functionCREATE FUNCTION dbo.fnGetAllCombinations
(
@WantedSum MONEY,
@GetOnlyFirstMatch BIT = 1,
@NicerLoopLook BIT = 0
)
RETURNS @Data TABLE (Loop INT, UniqueID VARCHAR(12), Number MONEY)
AS
BEGIN
-- Stage the data
DECLARE @Stage TABLE (RowID INT IDENTITY(0, 1), Number MONEY, UniqueID VARCHAR(12))
-- If all numbers are valid, add all but those equal to zero
IF EXISTS (SELECT NULL FROM [Sample] WHERE Number < 0)
INSERT @Stage
(
Number,
UniqueID
)
SELECT Number,
UniqueID
FROM [Sample]
WHERE Number <> 0
ELSE
INSERT @Stage
(
Number,
UniqueID
)
SELECT Number,
UniqueID
FROM [Sample]
WHERE Number > 0
AND Number <= @WantedSum
ORDER BY Number DESC
-- Create the control mechanism
DECLARE @Control TABLE (Bit SMALLINT IDENTITY(0, 1) PRIMARY KEY, Value TINYINT)
DECLARE @Value TINYINT,
@Mem TINYINT,
@Items INT,
@Loop INT
SELECT @Items = COUNT(*),
@Mem = 1,
@Loop = 1
FROM @Stage
-- Add a vertical binary counter
INSERT @Control
(
Value
)
SELECT 1
WHILE @Mem < @Items
BEGIN
INSERT @Control
(
Value
)
SELECT 0
SELECT @Mem = @Mem + 1
END
-- Work with the data
WHILE EXISTS (SELECT NULL FROM @Control WHERE Value = 1)
BEGIN
INSERT @Data
(
Loop,
UniqueID,
Number
)
SELECT @Loop,
s.UniqueID,
s.Number
FROM @Stage AS s
INNER JOIN @Control AS c ON c.Bit = s.RowID
WHERE c.Value = 1
IF (SELECT SUM(Number) FROM @Data WHERE Loop = @Loop) <> @WantedSum
DELETE
FROM @Data
WHERE Loop = @Loop
ELSE
IF @GetOnlyFirstMatch = 1
BREAK
SELECT @Mem = 1,
@Loop = @Loop + 1
UPDATE @Control
SET @Value = CASE WHEN Value + @Mem = 1 THEN 1 ELSE 0 END,
@Mem = CASE WHEN Value + @Mem = 2 THEN 1 ELSE 0 END,
Value = @Value
END
IF @NicerLoopLook = 1
UPDATE d1
SET d1.Loop = (SELECT COUNT(DISTINCT Loop) FROM @Data AS d2 WHERE d2.Loop <= d1.Loop)
FROM @Data AS d1
RETURN
END And use this sample test code to verify-- Prepare sample data
CREATE TABLE [Sample]
(
UniqueID VARCHAR(12),
Number MONEY,
)
INSERT [Sample]
SELECT 'a', -10 UNION ALL
SELECT 'b', 40 UNION ALL
SELECT 'c', 10 UNION ALL
SELECT 'd', -20 UNION ALL
SELECT 'e', 10 UNION ALL
SELECT 'f', 40
-- Show some results for the sum of 20
SELECT * FROM dbo.fnGetAllCombinations(20, 1, 0)
SELECT * FROM dbo.fnGetAllCombinations(20, 1, 1)
SELECT * FROM dbo.fnGetAllCombinations(20, 0, 0)
SELECT * FROM dbo.fnGetAllCombinations(20, 0, 1)
DROP TABLE [Sample] EDIT: If the numbers are all positive, we can optimize the algorithm by trying to sum up with the largest values first!
Peter Larsson Helsingborg, Sweden |
Edited by - SwePeso on 01/26/2007 05:22:14 |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 01/26/2007 : 02:40:52
|
For the wanted sum of 20, this is the result from the function above1 b 40.0000
1 d -20.0000
2 a -10.0000
2 b 40.0000
2 c 10.0000
2 d -20.0000
3 c 10.0000
3 e 10.0000
4 a -10.0000
4 b 40.0000
4 d -20.0000
4 e 10.0000
5 d -20.0000
5 f 40.0000
6 a -10.0000
6 c 10.0000
6 d -20.0000
6 f 40.0000
7 a -10.0000
7 d -20.0000
7 e 10.0000
7 f 40.0000
Peter Larsson Helsingborg, Sweden |
 |
|
|
rockmoose
SQL Natt Alfen
Sweden
3279 Posts |
Posted - 01/26/2007 : 04:45:10
|
Good!
The default recursion level for CTE is 100. You can use MAXRECURSION hint and set it to 0, which means unlimited.
rockmoose |
 |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
|
| |
Topic  |
|
|
|