looking for algorithem - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

SQL Server Development (2000)

looking for algorithem

Author

Topic

pelegk2
Aged Yak Warrior

723 Posts

Posted - 2007-01-24 : 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)

17689 Posts

Posted - 2007-01-24 : 04:52:27

[code]
select id
from tbl
group by id
having sum(number) <= @given_value + 10
and sum(number) >= @given_value - 10
[/code]

pelegk2
Aged Yak Warrior

723 Posts

Posted - 2007-01-24 : 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)

17689 Posts

Posted - 2007-01-24 : 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 ?

pelegk2
Aged Yak Warrior

723 Posts

Posted - 2007-01-24 : 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

30421 Posts

Posted - 2007-01-24 : 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

pelegk2
Aged Yak Warrior

723 Posts

Posted - 2007-01-24 : 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

30421 Posts

Posted - 2007-01-24 : 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

khtan
In (Som, Ni, Yak)

17689 Posts

Posted - 2007-01-24 : 19:58:55

Excellent work Peter

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-25 : 00:55:41

Thanks.
It took some thinking for converting my normal horizontal binary counter to a vertical equivalent.

Enjoy!

Peter Larsson
Helsingborg, Sweden

pelegk2
Aged Yak Warrior

723 Posts

Posted - 2007-01-25 : 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

30421 Posts

Posted - 2007-01-25 : 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

30421 Posts

Posted - 2007-01-25 : 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

723 Posts

Posted - 2007-01-25 : 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

3279 Posts

Posted - 2007-01-25 : 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

30421 Posts

Posted - 2007-01-26 : 02:38:05

How many recursive calls does SQL Server 2005 accept?

~~Here is my original function~~

CREATE 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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-26 : 02:40:52

For the wanted sum of 20, this is the result from the function above

1	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

3279 Posts

Posted - 2007-01-26 : 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

30421 Posts

Posted - 2007-03-14 : 06:20:37

Also see here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=79505

Peter Larsson
Helsingborg, Sweden

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources