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)
 Mathematically challenged query

Author  Topic 

Hommer
Aged Yak Warrior

808 Posts
Posted - 2004-12-16 : 09:49:26
To those mathematically gifted SQL Gurus, I need your help. The question seems simple, but the solution may not.

Here is the simplified sample data.

CREATE TABLE [dbo].[MathTest] (
[Pid] [int] IDENTITY (1, 1) NOT NULL ,
[Amt] [int] NULL
) ON [PRIMARY]
GO

insert into mathtest (Amt) Values (-10)
insert into mathtest (Amt) Values (-8)
insert into mathtest (Amt) Values (-7)
insert into mathtest (Amt) Values (-4)
insert into mathtest (Amt) Values (-1)
insert into mathtest (Amt) Values (2)
insert into mathtest (Amt) Values (5)
insert into mathtest (Amt) Values (13)
insert into mathtest (Amt) Values (20)

The question is: in what combinations of entry will yield to a total of 6?

So the answers for above set of data will include:

13+(-7) = 6
or adding amt of pid = 8 and pid = 3.

20+(-10)+(-4)=6
or pid 9, 1, and 4

5+2+(-1) = 6
or pid 7, 6, and 5.

Of cause, I got these answers by doing the math, now I want to come up with a t-sql script that can do the search for me. The real table has 3000 records, and as you may already guess correctly, it is an accounting application.

Thanks!

Andraax
Aged Yak Warrior

790 Posts
Posted - 2004-12-16 : 10:25:02
Hi!

How many combinations do you want to search for? If all possible, then it will take huge amounts of time. If you have a set limit of amounts to combine, you can cross join the table with itself over and over to produce the desired result.

/Andraax
Go to Top of Page

Hommer
Aged Yak Warrior

808 Posts
Posted - 2004-12-16 : 10:55:57
I really don't know, but let's say try up to 10 at first run. Or in the sample above, try adding up any combination of 2 amts and 3 amts, but ignore 4, 5, to all 9.

Cross join! I was thinking alone the line of using cursor to loop through it.

Go to Top of Page

robvolk
Most Valuable Yak

15732 Posts
Posted - 2004-12-16 : 11:31:36
Yeah, but to cross join this 3000 row table once (for a+b combos) will give you 9 million rows; twice (for a+b+c) will give you 27 billion rows. There's no way you can extend it to 10 variables.

Dare I ask why someone wants to do this anyway? Seriously, it's a pretty dumb requirement.
Go to Top of Page

jbkayne
Posting Yak Master

100 Posts
Posted - 2004-12-16 : 12:04:55

-----------------------
-- Handles Comb of 2's
-----------------------
select math1.Pid as Pid1
, math1.Amt as Pid1_Amt
, math2.Pid as Pid2
, math2.Amt as Pid2_Amt
, null as Pid3
, null as Pid3_Amt
from mathtest as math1
inner join mathtest as math2
on math1.Amt + math2.Amt = 6
and math1.Pid < math2.Pid

union


-----------------------
-- Handles Comb of 3's
-----------------------
select math1.Pid as Pid1
, math1.Amt as Pid1_Amt
, math2.Pid2
, math2.Pid2_Amt
, math2.Pid3
, math2.Pid3_Amt

from mathtest as math1
inner join (
select math1inner.Pid as Pid2
, math1inner.Amt as Pid2_Amt
, math2inner.Pid as Pid3
, math2inner.Amt as Pid3_Amt
, math1inner.Amt + math2inner.Amt as Sum2and3
from mathtest as math1inner
inner join mathtest as math2inner
on math1inner.Pid < math2inner.Pid
) as math2
on math1.Amt + Sum2and3 = 6
and math1.Pid < math2.Pid2
and math1.Pid < math2.Pid3
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-12-16 : 12:05:33
actually, i think it gets even worse:

if there are X numbers, then there are 2^X possible combinations possible that you'd need to check.

that means, for 30 numbers, you'd need to check 1,073,741,824 different combinations! now, if you are looking for combos of any 2 numbers, or no more than any 3 numbers, you can reduce this dramatically. with 30 numbers, for any two, there would be 30*29 =870 possibilities; for any 3, there'd be 30*29*28 =24,360 possibilities.

(it's been a while since probability class, but I think I am correct or at least close with these calcs)

if all the numbers were positive, this would be easier, since you could eliminate all numbers > your target value. but the existence of negative numbers don't let you do this.



- Jeff
Go to Top of Page

Hommer
Aged Yak Warrior

808 Posts
Posted - 2004-12-16 : 12:06:04
Now I got this cross join to get the Cartesian product of two amts,
select a.pid apid, a.amt aamt, b.pid bpid, b.amt bamt, a.amt+ b.amt total
from mathtest a cross join mathtest b
where a.amt+ b.amt=6

There is one problem. apid=8 and bpid=3 are same as apid=3 and bpid=8. I only need one but not both.

Furthermore, when I used following to cross join amt three times, besides above issue, I also got same amt being used twice, such as (-7)+(-7)+20=6.

Any idea how to improve my query? Thanks!

select a.pid apid,a.amt aamt,
b.pid bpid, b.amt bamt, a.amt+ b.amt abtotal,
c.pid cpid, c.amt camt, a.amt+b.amt+c.amt abcTotal
from mathtest a cross join mathtest b cross join mathtest c
where a.amt+ b.amt+c.amt=6
Go to Top of Page

Hommer
Aged Yak Warrior

808 Posts
Posted - 2004-12-16 : 12:21:41
Sorry I did not see JB's last post when I typed up my own.
His script works.

When I applied to real data, 2 combo took 1 second to complete, and it took 45 seconds if without where clause.

I will try 3, 4, and see how far I can go.

I know it is a dumb requirement. Actually it is not a requirement, but they are running out of way to find the niddle in the haystack, and ask IT to see we could offer any help.
Go to Top of Page

Arnold Fribble
Yak-finder General

1961 Posts
Posted - 2004-12-16 : 12:48:56
subset sum
NP complete
Go to Top of Page

Bustaz Kool
Master Smack Fu Yak Hacker

1834 Posts
Posted - 2004-12-16 : 12:57:28
To limit the processing, you don't really need to perform a cross join. You could join on t1.Amt >= t2.Amt and t1.PK <> t2.PK.

HTH

=================================================================

Happy Holidays!
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2004-12-16 : 13:33:17
Here's what i did... its still a lot of work to expand this to a ton of variables:


Create Table #mathTest (n int)

insert into #mathtest (n) Values (-28)
insert into #mathtest (n) Values (-25)
insert into #mathtest (n) Values (-17)
insert into #mathtest (n) Values (-13)
insert into #mathtest (n) Values (-10)
insert into #mathtest (n) Values (-8)
insert into #mathtest (n) Values (-7)
insert into #mathtest (n) Values (-4)
insert into #mathtest (n) Values (-1)
insert into #mathtest (n) Values (2)
insert into #mathtest (n) Values (5)
insert into #mathtest (n) Values (13)
insert into #mathtest (n) Values (20)
insert into #mathtest (n) Values (27)
insert into #mathtest (n) Values (32)
insert into #mathtest (n) Values (34)
insert into #mathtest (n) Values (41)

Declare @sumTotal int
Set @sumTotal = 6


--Two variables
Select 
	A.n,
	B.n,
	A.n + B.n
From #mathTest A
Inner Join #mathTest B
On A.n + B.n = @sumTotal
and A.n <= B.n


--Three variables
Select 
	A.n,
	B.n,
	C.n,
	A.n + B.n + C.n
From #mathTest A
Inner Join #mathTest B
On A.n + B.n <> @sumTotal
and A.n <= B.n
Inner Join #mathTest C
On A.n + B.n + C.n = @sumTotal
and B.n <= C.n


--Four variables
Select 
	A.n,
	B.n,
	C.n,
	D.n,
	A.n + B.n + C.n + D.n
From #mathTest A
Inner Join #mathTest B
On A.n + B.n <> @sumTotal
and A.n <= B.n
Inner Join #mathTest C
On A.n + B.n + C.n <> @sumTotal
and B.n <= C.n
Inner Join #mathTest D
On A.n + B.n + C.n + D.n = @sumTotal
and C.n <= D.n

Drop Table #mathTest


Corey
Go to Top of Page

jsmith8858
Dr. Cross Join

7423 Posts
Posted - 2004-12-16 : 14:03:12
quote:

I know it is a dumb requirement. Actually it is not a requirement, but they are running out of way to find the niddle in the haystack, and ask IT to see we could offer any help.

let me guess: accounting department? something is out of balance by X dollars and they can't tell why?

- Jeff
Go to Top of Page

Bustaz Kool
Master Smack Fu Yak Hacker

1834 Posts
Posted - 2004-12-16 : 16:02:58
Your join condition still needs to impose the requirement that the same row is not being joined with itself. Otherwise a single row's value (e.g., 11) could be used twice to arrive at the total (e.g., 22).

HTH

=================================================================

Happy Holidays!
Go to Top of Page

Seventhnight
Master Smack Fu Yak Hacker

2878 Posts
Posted - 2004-12-16 : 19:58:18
quote:
Originally posted by Bustaz Kool

Your join condition still needs to impose the requirement that the same row is not being joined with itself. Otherwise a single row's value (e.g., 11) could be used twice to arrive at the total (e.g., 22).

HTH

=================================================================

Happy Holidays!


So change all of the <='s to <'s

Corey
Go to Top of Page

Bustaz Kool
Master Smack Fu Yak Hacker

1834 Posts
Posted - 2004-12-17 : 01:14:38
Corey,

This would not cover the instance where two rows contain the same value for Amt.

HTH

=================================================================

Happy Holidays!
Go to Top of Page
   

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources

Articles

Forums

Blogs

Contact Us

About the Site