Summed Combinations of an array

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

Transact-SQL (2000)

Summed Combinations of an array

Author

Topic

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-19 : 13:01:02

Guys,
Been working on this gem in SQL2005 but have not come up with a clean solution just yet. My first crack uses Cross Apply, but Im open to SQL2000 solutions as well.

@Process is a collection of elements (a tabled array).
@ProcessStage is a subset of these elements.

ProcessValue is unique.

I want the sum(ProcessValue) for each possible combination of the element subset.

declare @Process table (ProcessID int, ProcessValue int)
insert into @Process
	select 1, 1 union 
	select 2, 2 union 
	select 3, 4 union 
	select 4, 8 union 
	select 5, 16

declare @ProcessStage table (ProcessID int)
insert into @ProcessStage
	select 1 union 
	select 3 union 
	select 4

select	d.ProcessValueSum
from @Process dp
CROSS APPLY
		(	select	sum(ddp.ProcessValue) ProcessValueSum
			from @Process ddp 
			join @ProcessStage ps
				on ddp.ProcessID = ps.ProcessID
			where ddp.ProcessValue <> dp.ProcessValue
		) d
union
select d.ProcessValueSum
from @Process dp
CROSS APPLY
		(	select	sum(ddp.ProcessValue) ProcessValueSum
			from @Process ddp 
			join @ProcessStage ps
				on ddp.ProcessID = ps.ProcessID
			where ddp.ProcessValue = dp.ProcessValue
		) d
where ProcessValueSum is not null
order by 1

-- Desired resultset:
--1	-- sum(1)
--4	-- sum(4)
--5	-- sum(1+4)
--8	-- sum(8)
--9	-- sum(1+8)
--12	-- sum(8+4)
--13	-- sum(1+4+8)

Nathan Skerl

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-19 : 14:09:41

I think this code will do the trick for any combinations you can come up with!
As long as there are less than 64 matches between Process table and ProcessStage table.

-- Prepare test data.
declare @Process table (ProcessID int, ProcessValue int)

insert into @Process
	select 1, 1 union 
	select 2, 2 union 
	select 3, 4 union 
	select 4, 8 union 
	select 5, 16

declare @ProcessStage table (ProcessID int)

insert into @ProcessStage
	select 1 union 
	select 3 union 
	select 4

-- The work start here. Stage the work data for faster processing.
DECLARE	@stage	TABLE (ID INT IDENTITY(0, 1), bin BIGINT, Value INT)

INSERT		@stage (Value)
SELECT		p.ProcessValue
FROM		@Process p
INNER JOIN	@ProcessStage ps ON ps.ProcessID = p.ProcessID

update	@stage
set	bin = power(2, id)

-- Do the magic!
declare @output table (ProcessValueSum bigint)

declare	@sum bigint,
	@mem bigint,
	@bin bigint

select	@bin = sum(bin),
	@mem = sum(bin),
	@sum = 0
from	@stage

while	@mem > 0
	begin
		select	@sum = @sum + case when z.bin <= @bin then z.value else 0 end,
			@bin = @bin - case when z.bin <= @bin then z.bin else 0 end
		from	(
				select	top 100 percent bin, value from @stage order by bin desc
			) z

		insert	@output
		select	@sum

		select	@mem = @mem - 1,
			@bin = @mem,
			@sum = 0
	end

select * from @output

ProcessValueSum
---------------
             13
             12
              9
              8
              5
              4
              1

This is my first draft. I will probably come up with something more clever in a while.

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 02:38:46

Here is a generic solution that does not have the limit mentioned in my previous post.
Please note that calculating all 63 permutations take a very long time, since that is 9,223,372,036,854,775,800 combinations.

Here is the code

-- Prepare test data.
declare @Process table (ProcessID int, ProcessValue int)

insert into @Process
	select 1, 1 union 
	select 2, 2 union 
	select 3, 4 union 
	select 4, 8 union 
	select 5, 16

declare @ProcessStage table (ProcessID int)

insert into @ProcessStage
	select 1 union 
	select 3 union 
	select 4

-- The work start here. Stage the work data for faster processing.
DECLARE	@stage	TABLE (RowID INT IDENTITY(0, 1) primary key clustered, bin TINYINT default 0, pValue INT)

INSERT		@stage (pValue)
SELECT		p.ProcessValue
FROM		@Process p
INNER JOIN	@ProcessStage ps ON ps.ProcessID = p.ProcessID

-- Do the magic!
declare @output table (ProcessValueSum int)

declare	@row int,
	@sum int

select	@row = 0

while	@row is not null
	begin
		update	@stage
		set	bin = 0
		where	rowid < @row

		update	@stage
		set	bin = 1
		where	rowid = @row

		insert	@output
		select	sum(pvalue)
		from	@stage
		where	bin = 1

		select	@row = min(rowid)
		from	@stage
		where	bin = 0
	end

select * from @output

ProcessValueSum
---------------
              1
              4
              5
              8
              9
             12
             13

Peter Larsson
Helsingborg, Sweden

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-20 : 11:27:03

Nice work Peter!

Do you think its possible without a loop?

I can see using a cross join per array value, but thats hard to do considering we dont know the number of array values passed in.

Nathan Skerl

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 11:33:07

Yes, it is possible to do, but only if you know how many permutations there will be at most at any given time.

Or always calculate no more than 8 permutations at any given time.
SELECT TOP 8, SELECT NEXT TOP 8 and so on? Will that do? With this approach you have more control over execution.

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 11:48:45

Or you can use dynamic SQL to do the trick?

But remember that calculating all permutations is 2^(numbers in array), so this value quickly grows to eternity...

Peter Larsson
Helsingborg, Sweden

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-20 : 11:48:48

In my case, the array is always <= 6 elements.

So that would give us a max permutation value of 64.

Nathan Skerl

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 11:51:01

quote:
Originally posted by nathans

In my case, the array is <= 6 always

Nathan Skerl

Ok, give me 30 minutes...

Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 12:21:16

Why is it important to do without a loop? My second post will take care of any vector sizes.

-- Prepare test data.
declare @Process table (ProcessID int, ProcessValue int)

insert into @Process
	select 1, 1 union 
	select 2, 2 union 
	select 3, 4 union 
	select 4, 8 union 
	select 5, 16

declare @ProcessStage table (ProcessID int)

insert into @ProcessStage
	select 1 union 
	select 3 union 
	select 4

-- The work start here. Stage the work data for faster processing.
DECLARE	@stage TABLE (ID INT IDENTITY(1, 1), Value INT)

INSERT		@stage
SELECT		p.ProcessValue
FROM		@Process p
INNER JOIN	@ProcessStage ps ON ps.ProcessID = p.ProcessID

DECLARE	@p1 INT,
	@p2 INT,
	@p3 INT,
	@p4 INT,
	@p5 INT,
	@p6 INT

SELECT @p1 = Value FROM @Stage WHERE ID = 1
SELECT @p2 = Value FROM @Stage WHERE ID = 2
SELECT @p3 = Value FROM @Stage WHERE ID = 3
SELECT @p4 = Value FROM @Stage WHERE ID = 4
SELECT @p5 = Value FROM @Stage WHERE ID = 5
SELECT @p6 = Value FROM @Stage WHERE ID = 6

-- Do the magic!
declare @output table (ProcessValueSum bigint)

INSERT		@Output
SELECT		SUM(
			CASE WHEN z.i / 32 % 2 = 1 THEN @p1 ELSE 0 END +
			CASE WHEN z.i / 16 % 2 = 1 THEN @p2 ELSE 0 END +
			CASE WHEN z.i / 8 % 2 = 1 THEN @p3 ELSE 0 END +
			CASE WHEN z.i / 4 % 2 = 1 THEN @p4 ELSE 0 END +
			CASE WHEN z.i / 2 % 2 = 1 THEN @p5 ELSE 0 END +
			CASE WHEN z.i / 1 % 2 = 1 THEN @p6 ELSE 0 END
		) T
FROM		(
			SELECT		b0.i +  b1.i + b2.i + b3.i + b4.i + b5.i i
			FROM		(SELECT 0 i UNION ALL SELECT 1) b0
			CROSS JOIN	(SELECT 0 i UNION ALL SELECT 2) b1
			CROSS JOIN	(SELECT 0 i UNION ALL SELECT 4) b2
			CROSS JOIN	(SELECT 0 i UNION ALL SELECT 8) b3
			CROSS JOIN	(SELECT 0 i UNION ALL SELECT 16) b4
			CROSS JOIN	(SELECT 0 i UNION ALL SELECT 32) b5
		) z
WHERE		z.i > 0
GROUP BY	z.i

SELECT		ProcessValueSum
FROM		@Output
WHERE		ProcessValueSum IS NOT NULL
ORDER BY	ProcessValueSum

Peter Larsson
Helsingborg, Sweden

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-20 : 12:28:50

No, not important, I was just curious how it would be done. I love seeing t-sql extended (over extended?) to solve these math probs.

Great work!! I learned a lot on this one.

Nathan Skerl

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 12:34:00

Are you reading about polynomic calculations in school?

Peter Larsson
Helsingborg, Sweden

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-20 : 12:47:04

Well, yes... but not in school any longer

. Its been years since I studied this stuff, but this example has really got me tinkering again.

This question stems from a generic rules engine I am developing, the elements being various qualifying attributes (Age, sex, etc.) and the ProcessID being an group classification.

Im glad to have you as a resource, thanks again!

Nathan Skerl

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-20 : 12:50:17

If you know of any online resources I should check out please pass them on. Im always looking for knowledge!

Nathan Skerl

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-07-20 : 15:46:58

I could not resist this one. I don't think I can get it more simplified than this

-- Prepare test data.
declare @Process table (ProcessID int, ProcessValue int)

insert into @Process
	select 1, 1 union 
	select 2, 2 union 
	select 3, 4 union 
	select 4, 8 union 
	select 5, 16

declare @ProcessStage table (ProcessID int)

insert into @ProcessStage
	select 1 union 
	select 3 union 
	select 4

-- The work start here. Stage the work data for faster processing.
DECLARE	@stage TABLE (ID INT IDENTITY(1, 1), Value INT)

INSERT		@stage
SELECT		p.ProcessValue
FROM		@Process p
INNER JOIN	@ProcessStage ps ON ps.ProcessID = p.ProcessID

DECLARE	@p1 INT,
	@p2 INT,
	@p3 INT,
	@p4 INT,
	@p5 INT,
	@p6 INT

SELECT @p1 = Value FROM @Stage WHERE ID = 1
SELECT @p2 = Value FROM @Stage WHERE ID = 2
SELECT @p3 = Value FROM @Stage WHERE ID = 3
SELECT @p4 = Value FROM @Stage WHERE ID = 4
SELECT @p5 = Value FROM @Stage WHERE ID = 5
SELECT @p6 = Value FROM @Stage WHERE ID = 6

-- Do the magic!
SELECT DISTINCT	b1.i * ISNULL(@p1, 0) +
		b2.i * ISNULL(@p2, 0) +
		b3.i * ISNULL(@p3, 0) +
		b4.i * ISNULL(@p4, 0) +
		b5.i * ISNULL(@p5, 0) +
		b6.i * ISNULL(@p6, 0) Num
FROM		(SELECT 0 i UNION ALL SELECT 1) b1
CROSS JOIN	(SELECT 0 i UNION ALL SELECT 1) b2
CROSS JOIN	(SELECT 0 i UNION ALL SELECT 1) b3
CROSS JOIN	(SELECT 0 i UNION ALL SELECT 1) b4
CROSS JOIN	(SELECT 0 i UNION ALL SELECT 1) b5
CROSS JOIN	(SELECT 0 i UNION ALL SELECT 1) b6
WHERE		b1.i * ISNULL(@p1, 0) +
		b2.i * ISNULL(@p2, 0) +
		b3.i * ISNULL(@p3, 0) +
		b4.i * ISNULL(@p4, 0) +
		b5.i * ISNULL(@p5, 0) +
		b6.i * ISNULL(@p6, 0) > 0

Peter Larsson
Helsingborg, Sweden

nathans
Aged Yak Warrior

938 Posts

Posted - 2006-07-20 : 20:30:13

yup, that is clean. Great job.

Nathan Skerl

RyanRandall
Master Smack Fu Yak Hacker

1074 Posts

Posted - 2006-07-21 : 07:00:09

Here's another method using a numbers table (which can be found here: http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=47685).

--data
declare @Process table (ProcessID int, ProcessValue int)
insert @Process
	select 1, 1 union 
	select 2, 2 union 
	select 3, 4 union 
	select 4, 8 union 
	select 5, 16

declare @ProcessStage table (ProcessID int)
insert @ProcessStage
	select 1 union 
	select 3 union 
	select 4

--calculation
DECLARE	@stage TABLE (i INT IDENTITY(0, 1), v INT)

INSERT		@stage
SELECT		p.ProcessValue
FROM		@Process p
INNER JOIN	@ProcessStage ps ON ps.ProcessID = p.ProcessID

declare @NumberCount int
select @NumberCount = power(2, count(*)) from @stage

select sum(case when x > 0 then v end) as x
from (select v, NUMBER, NUMBER & power(2, i) as x  from @stage, dbo.F_TABLE_NUMBER_RANGE(1, @NumberCount)) a
group by NUMBER having sum(case when x > 0 then v end) is not null

/*results
x           
----------- 
1
4
5
8
9
12
13
*/

Ryan Randall
www.monsoonmalabar.com London-based IT consultancy

Solutions are easy. Understanding the problem, now, that's the hard part.

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources