SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 SQL Server 2000 Forums
 SQL Server Development (2000)
 looking for algorithem
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

pelegk2
Aged Yak Warrior

Israel
723 Posts

Posted - 01/24/2007 :  04:42:53  Show Profile  Visit pelegk2's Homepage  Send pelegk2 an ICQ Message  Reply with Quote
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
17430 Posts

Posted - 01/24/2007 :  04:52:27  Show Profile  Reply with Quote

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



KH

Go to Top of Page

pelegk2
Aged Yak Warrior

Israel
723 Posts

Posted - 01/24/2007 :  05:57:56  Show Profile  Visit pelegk2's Homepage  Send pelegk2 an ICQ Message  Reply with Quote
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 -:)
Go to Top of Page

khtan
In (Som, Ni, Yak)

Singapore
17430 Posts

Posted - 01/24/2007 :  06:16:19  Show Profile  Reply with Quote
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

Go to Top of Page

pelegk2
Aged Yak Warrior

Israel
723 Posts

Posted - 01/24/2007 :  06:20:31  Show Profile  Visit pelegk2's Homepage  Send pelegk2 an ICQ Message  Reply with Quote
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 -:)
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/24/2007 :  06:53:12  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Go to Top of Page

pelegk2
Aged Yak Warrior

Israel
723 Posts

Posted - 01/24/2007 :  08:08:34  Show Profile  Visit pelegk2's Homepage  Send pelegk2 an ICQ Message  Reply with Quote
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 -:)
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/24/2007 :  17:49:59  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Go to Top of Page

khtan
In (Som, Ni, Yak)

Singapore
17430 Posts

Posted - 01/24/2007 :  19:58:55  Show Profile  Reply with Quote
Excellent work Peter


KH

Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/25/2007 :  00:55:41  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Go to Top of Page

pelegk2
Aged Yak Warrior

Israel
723 Posts

Posted - 01/25/2007 :  03:48:30  Show Profile  Visit pelegk2's Homepage  Send pelegk2 an ICQ Message  Reply with Quote
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 -:)
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/25/2007 :  04:24:36  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/25/2007 :  04:28:30  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Go to Top of Page

pelegk2
Aged Yak Warrior

Israel
723 Posts

Posted - 01/25/2007 :  13:11:20  Show Profile  Visit pelegk2's Homepage  Send pelegk2 an ICQ Message  Reply with Quote
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 -:)
Go to Top of Page

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 01/25/2007 :  20:18:46  Show Profile  Reply with Quote
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
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/26/2007 :  02:38:05  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Edited by - SwePeso on 01/26/2007 05:22:14
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 01/26/2007 :  02:40:52  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Go to Top of Page

rockmoose
SQL Natt Alfen

Sweden
3279 Posts

Posted - 01/26/2007 :  04:45:10  Show Profile  Reply with Quote
Good!

The default recursion level for CTE is 100.
You can use MAXRECURSION hint and set it to 0, which means unlimited.

rockmoose
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
29909 Posts

Posted - 03/14/2007 :  06:20:37  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Also see here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=79505


Peter Larsson
Helsingborg, Sweden
Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.17 seconds. Powered By: Snitz Forums 2000