April 14, 2010 at 10:03 am
mike 97607
You might want to read these 2 articles, starting with Jeff Moden's
http://www.sqlservercentral.com/articles/T-SQL/68467/
and then going on to Lynn Pettis's article
http://www.sqlservercentral.com/articles/T-SQL/65522/
Both are excellent explanations and contain sample code. Combined, these might give you a new perspective on a possible solution to your problem.
In either case both articles are excellent reads ...
April 15, 2010 at 6:50 am
Here's something that I came up with that kinda works, it has one flaw where if it finds a match with 1,7,8, it will also find a match with 1,8,7 and it's a little ugly. I do appreciate everyone's assistance, thank you.
SET NOCOUNT ON
DECLARE @source TABLE (ID int, Amount float)
DECLARE @results TABLE (ID varchar(MAX), Amount float)
DECLARE @amount float
DECLARE @index int
DECLARE @rowcount int
INSERT INTO @source VALUES(1, 1.00)
INSERT INTO @source VALUES(2, 1.33)
INSERT INTO @source VALUES(3, 3.67)
INSERT INTO @source VALUES(4, 4.00)
INSERT INTO @source VALUES(5, 5.33)
INSERT INTO @source VALUES(6, 5.00)
INSERT INTO @source VALUES(7, 3.00)
INSERT INTO @source VALUES(8, 2.33)
INSERT INTO @source VALUES(9, 9.33)
SET @amount=9.33
SELECT @index=1,@rowcount=COUNT(*) FROM @source WHERE Amount<=@amount
INSERT INTO @results (ID,Amount)
SELECT CONVERT(varchar, ID),Amount FROM @source
WHERE Amount<=@amount
WHILE (@index<@rowcount)
BEGIN
INSERT INTO @results (ID,Amount)
SELECT CONVERT(varchar, A.ID)+','+CONVERT(varchar, B.ID),A.Amount+B.Amount
FROM @results A INNER JOIN @source B ON (A.ID!=CONVERT(varchar, B.ID))
WHERE A.ID<CONVERT(varchar, B.ID)
AND PATINDEX('%,'+CONVERT(varchar, B.ID)+'%', CONVERT(varchar, A.ID))=0
AND A.Amount+B.Amount<=@amount
AND CONVERT(varchar, A.ID)+','+CONVERT(varchar, B.ID) NOT IN (SELECT ID FROM @results)
ORDER BY A.ID
IF @@ROWCOUNT=0
BREAK
SET @index=@index+1
END
DELETE FROM @results WHERE Amount!=@amount
SELECT * FROM @results ORDER BY ID
SET NOCOUNT OFF
April 15, 2010 at 7:13 am
hi buddy... i have created one code for you, test this if it works...
IMPORTANT:
I HAVE USED PAUL WHITE NZ'S N-WAY HANDSHAKING COMBINATIONS TO SCRIPT THIS. SO ALL CREDIT TO HIM FOR CODING SUCH A BEAUTIFUL PIECE OF CODE..
Here is your code:
IF OBJECT_ID('BILL_MONEY') IS NOT NULL
DROP TABLE BILL_MONEY
CREATE TABLE BILL_MONEY
(
BILL_ID INT IDENTITY(1,1) CONSTRAINT PK_BILL_ID_BILL_MONEY PRIMARY KEY,
AMOUNT MONEY
)
INSERT INTO BILL_MONEY
SELECT 10.00
UNION ALL
SELECT 5.00
UNION ALL
SELECT 2.00
UNION ALL
SELECT 5.00
UNION ALL
SELECT 3.33
UNION ALL
SELECT 1.20
UNION ALL
SELECT 8.70
UNION ALL
SELECT 9.99
UNION ALL
SELECT 19.82
UNION ALL
SELECT 0.67
SELECT * FROM BILL_MONEY
DECLARE @Bits
TABLE (
bit_id BIGINT NOT NULL PRIMARY KEY,
value BIGINT NOT NULL
);
INSERT @Bits (bit_id, value)
SELECT P.ID - 1, POWER(2, (P.ID - 1))
FROM (SELECT ROW_NUMBER() OVER(ORDER BY BILL_ID) AS ID FROM BILL_MONEY ) P;
DECLARE @Grouped
TABLE (
N BIGINT NOT NULL,
BILL_ID INT NOT NULL,
group_size BIGINT NOT NULL,
group_order BIGINT NOT NULL,
group_row BIGINT NOT NULL
);
INSERT @Grouped
(N,BILL_ID, group_size, group_order, group_row)
SELECT Q.N,
Q.BILL_ID,
Q.group_size,
group_order = DENSE_RANK() OVER (PARTITION BY Q.group_size ORDER BY Q.N),
group_row = DENSE_RANK() OVER (PARTITION BY Q.group_size ORDER BY Q.BILL_ID)
FROM (
SELECT N.N,
P.BILL_ID BILL_ID,
group_size = COUNT(*) OVER (PARTITION BY N.N)
FROM dbo.Numbers (POWER(2, (SELECT COUNT(*) FROM BILL_MONEY))) N
JOIN @Bits B
ON N.N & B.value = B.value
JOIN (SELECT ROW_NUMBER() OVER(ORDER BY BILL_ID) AS ID , BILL_ID FROM BILL_MONEY ) P
ON P.ID = B.bit_id
) Q
;WITH CTE (RID , COMBINATIONS) AS
(
SELECT ROW_NUMBER() OVER(PARTITION BY G.COMBINATIONS ORDER BY G.COMBINATIONS) RID , G.COMBINATIONS FROM (
SELECT COMBINATIONS =
STUFF
(
(
SELECT ',' + CAST (BILL_ID AS VARCHAR)
FROM @Grouped T2
WHERE T2.N = T1.N
ORDER BY
BILL_ID ASC
FOR XML PATH('')
)
, 1, 1, SPACE(0))
FROM @Grouped T1
WHERE group_row = 1
) G
)
DELETE FROM CTE WHERE RID <> 1
DECLARE @MATCHING_AMOUNT MONEY
SET @MATCHING_AMOUNT = 10.00
--SELECT
IF OBJECT_ID('TEMPDB..#COMBINATIONS') IS NOT NULL
DROP TABLE #COMBINATIONS
CREATE TABLE #COMBINATIONS (COMBINATIONS VARCHAR(4000))
DECLARE @sql NVARCHAR(MAX)
SET @sql = 'DECLARE @AMOUNT INT '
SELECT @sql =
@sql + 'SELECT @AMOUNT = SUM(AMOUNT) FROM BILL_AMOUNT WHERE BILL_ID IN ('+
STUFF
(
(
SELECT ',' + CAST (BILL_ID AS VARCHAR)
FROM @Grouped T2
WHERE T2.N = T1.N
ORDER BY
BILL_ID ASC
FOR XML PATH('')
)
, 1, 1, SPACE(0)) + ') IF @AMOUNT = '+ CAST (@MATCHING_AMOUNT AS VARCHAR) + ' BEGIN INSERT INTO #COMBINATIONS SELECT @AMOUNT' + CHAR(10)
FROM @Grouped T1
WHERE group_row = 1
--PRINT @sql
EXEC (@SQL)
SELECT * FROM #COMBINATIONS
April 15, 2010 at 7:28 am
Wow - thanks. One issue I found was dbo.Numbers does not exist. Can you please provide that too. Thanks
April 15, 2010 at 9:38 am
Thanks greatly to COldCoffee's post, which was way over my head of course, but I was able to pluck out the pieces that worked for me, specifically the bitwise pieces. From that, I think I now have a pretty decent solution. Hopes this helps someone else...
SET NOCOUNT ON
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED
DECLARE @source TABLE (BillID int,BillAmount money)
DECLARE @bits TABLE (BitID bigint NOT NULL PRIMARY KEY,BitValue bigint NOT NULL,BillID int,BillAmount money)
DECLARE @sumamounts TABLE (BitValue bigint, Amount money)
DECLARE @results TABLE (MatchID int, BillID int)
DECLARE @amount money
DECLARE @index int
DECLARE @rowcount int
SET @amount=8.33
INSERT INTO @source
SELECT 01, 1.00 UNION ALL
SELECT 02, 1.33 UNION ALL
SELECT 03, 3.67 UNION ALL
SELECT 04, 4.00 UNION ALL
SELECT 05, 1.33 UNION ALL
SELECT 06, 6.00 UNION ALL
SELECT 07, 3.00 UNION ALL
SELECT 08, 2.33 UNION ALL
SELECT 09, 9.33
INSERT INTO @bits (BitID,BitValue,BillID,BillAmount)
SELECT P.ID-1,POWER(2, (P.ID - 1)),P.BillID,P.BillAmount
FROM (SELECT ROW_NUMBER() OVER(ORDER BY BillID) AS ID,BillID,BillAmount
FROM @source WHERE BillAmount<=@amount) P
SELECT @index=1,@rowcount=COUNT(*) FROM @source WHERE BillAmount<=@amount
INSERT INTO @sumamounts (BitValue,Amount)
SELECT BitValue,BillAmount FROM @bits
WHERE BillAmount<=@amount
WHILE (@index<@rowcount)
BEGIN
INSERT INTO @sumamounts (BitValue,Amount)
SELECT A.BitValue+B.BitValue,A.Amount+B.BillAmount
FROM @sumamounts A
INNER JOIN @bits B ON (A.BitValue!=B.BitValue)
WHERE A.BitValue<B.BitValue
AND A.Amount+B.BillAmount<=@amount
AND A.BitValue+B.BitValue NOT IN (SELECT BitValue FROM @sumamounts)
ORDER BY A.BitValue
SET @index=@index+1
END
SELECT R.MatchID,B.BillID,B.BillAmount
FROM @sumamounts S
INNER JOIN @bits B ON (B.BitValue&S.BitValue=B.BitValue)
INNER JOIN (SELECT ROW_NUMBER()OVER (ORDER BY S1.BitValue) AS MatchID,S1.BitValue FROM @sumamounts S1
WHERE S1.Amount=@amount) R ON (R.BitValue=S.BitValue)
WHERE Amount=@amount
ORDER BY S.BitValue
SET NOCOUNT OFF
April 15, 2010 at 9:40 am
Again, this is from Paul White's post..the NUmbers function which creates numbers from 1 to N fast, i mean, very fast!! 🙂
CREATE FUNCTION dbo.Numbers
(@N BIGINT)
RETURNS TABLE
WITH SCHEMABINDING
AS RETURN
WITH
N1 AS (SELECT N = 1 UNION ALL SELECT 1),
N2 AS (SELECT N = 1 FROM N1 T, N1),
N3 AS (SELECT N = 1 FROM N2 T, N2),
N4 AS (SELECT N = 1 FROM N3 T, N3),
N5 AS (SELECT N = 1 FROM N4 T, N4),
N6 AS (SELECT N = 1 FROM N5 T, N5),
NM AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT 0)) AS N FROM N6)
SELECT TOP (@N)
N
FROM NM
WHERE N <= @N
ORDER BY
N ASC;
GO
April 15, 2010 at 9:44 am
mike 97607 (4/15/2010)
Thanks greatly to COldCoffee's post, which was way over my head of course,
Please toss over all of the "thanks" to our comrade Paul White from NZ :cool:.. am happy that your issue is resolved.. was a great question, first place and good reception too, from all the SSC heavy-weights..
Thanks and Cheers!! 🙂
April 15, 2010 at 9:52 am
Pretty cool.
"Keep Your Stick On the Ice" ..Red Green
April 18, 2010 at 8:46 pm
Always nice to find that I've answered a thread before I've seen it :laugh:
Thanks, Cold Coffee!
April 18, 2010 at 9:00 pm
Paul White NZ (4/18/2010)
Always nice to find that I've answered a thread before I've seen it :laugh:Thanks, Cold Coffee!
coool 😎
You're welcome mate 🙂
May 8, 2010 at 7:34 am
Damn... great idea. This is a "bin stacking" problem and I know people that would kill to have this as a truly scalable solution. The solution, as is, dies at 40 rows and creates almost 50000 rows internally at 20 rows. Changing the integer values to float values in all of the POWER functions helps but it still overwhelms the BIGINT data type at only 70 rows.
--Jeff Moden
Change is inevitable... Change for the better is not.
May 14, 2010 at 6:38 am
thanks for the kudos.
Yes, I agree, it grows exponentially as the number of rows increases. I would prefer a more elegant solution but for now this solution meets my needs since it's unlikely there will be more than 5-10 rows that I will be comparing against.
May 15, 2010 at 7:58 am
Jeff Moden (5/8/2010)
Damn... great idea. This is a "bin stacking" problem and I know people that would kill to have this as a truly scalable solution. The solution, as is, dies at 40 rows and creates almost 50000 rows internally at 20 rows. Changing the integer values to float values in all of the POWER functions helps but it still overwhelms the BIGINT data type at only 70 rows.
True. The problem is hard one, apparently "a combinatorial NP-hard problem":
Viewing 13 posts - 16 through 27 (of 27 total)
You must be logged in to reply to this topic. Login to reply