master gg,
kainis last week ko lang nabasa 'tong thread. i know its late na and most probably you already found the solution already ![Wink [;)]](/cs/emoticons/emotion-5.gif)
. anyway, share ko na lang din yun solution ko ![Big Smile [:D]](/cs/emoticons/emotion-2.gif)
hmm i have encountered this kind of problem na before, back on vb6 days pa hehehe, yung problem naman was to create a program that will give the all the possible combinations of cd tracks that can be transfered to a cassete tape. and the rule is, that each side of the tape will consume its maximum length. so yun, parang same scenario lang sya dito sa problem natin hehehe. bale inapply ko na lang ulit yung algo hehehe.
to explain naman yung approach ko, if we look at the nature of the problem that master gg gave, we can see easily see that it's a permutation problem, where in we need to find first all the DISTINCT permutations/combinations. then find the sum of each combination. in short BRUTE FORCE hehehe.
share ko din cguro yung steps that i wrote down before i started coding
1. find the formula for permutation
2. find the formula for distinct permutation (http://mathforum.org/dr.math/faq/faq.comb.perm.html)
3. create table for my sets
if exists (select * from dbo.sysobjects where id = object_id(N'[dbo].[RefValues]') and OBJECTPROPERTY(id, N'IsUserTable') = 1)
drop table [dbo].[RefValues]
GO
CREATE TABLE [dbo].[RefValues]
(
[RefValueID] [int] IDENTITY (1, 1) NOT FOR REPLICATION NOT NULL ,
[RefValue] [numeric](18, 0) NULL
) ON [PRIMARY]
GO
4. based on the formula, i need to create a function to compute factorial
CREATE FUNCTION [dbo].[ComputeFactorial]
( @nInput int
, @nLimit int = 0
, @nDirection int = 1
)
RETURNS float
AS
BEGIN
DECLARE @nFactorial float
DECLARE @nMultiplier float
SET @nMultiplier = 1
IF @nDirection <> 1
BEGIN
SET @nDirection = -1
SET @nMultiplier = @nInput
END
IF @nLimit = 0 OR @nLimit IS NULL OR @nLimit > @nInput
BEGIN
SET @nLimit = @nInput
END
SET @nFactorial = 1
WHILE @nLimit >= 1
BEGIN
SET @nFactorial = @nFactorial * @nMultiplier
SET @nMultiplier = @nMultiplier + @nDirection
SET @nLimit = @nLimit - 1
END
RETURN @nFactorial
END
5. create function to compute permutation of a given set and no. of subsets, i need it to validate the result of my query.
CREATE FUNCTION [dbo].[ComputePermutation]
(
@nSets float
, @nSubSets float
)
RETURNS float
AS
BEGIN
IF @nSubSets > @nSets
BEGIN
SET @nSubSets = @nSets
END
DECLARE @nTotalPermutation float
DECLARE @nFactorialSets float
DECLARE @nLoopSets float
DECLARE @nSubSetsPermutation float
DECLARE @nFactorialSubSets float
DECLARE @nLoopSubSets float
SET @nTotalPermutation = 0
WHILE @nSubSets >= 1
BEGIN
SET @nFactorialSets = @nSets
SET @nLoopSets = @nFactorialSets - 1
SET @nFactorialSubSets = 1
SET @nLoopSubSets = @nSubSets
SET @nSubSetsPermutation = 0
SELECT @nFactorialSets = dbo.ComputeFactorial(@nSets,@nSubSets,-1)
SELECT @nFactorialSubSets = dbo.ComputeFactorial(@nSubSets,@nSubSets,1)
SET @nSubSetsPermutation = @nFactorialSets / @nFactorialSubSets
SET @nTotalPermutation = @nTotalPermutation + @nSubSetsPermutation
SET @nSubSets = @nSubSets - 1
END
RETURN @nTotalPermutation
END
6. create a function to do the permutation/brute force process. my first goal was to create a cursorless approach baka kayang masundot sa cross join hehehe, pero saka na lang hehe result now refactor later! heheh. and during coding i came to realize na SP na lang muna gagamitin ko at wag muna function hehehe and i also need a split function kaya gumawa din ako.
CREATE FUNCTION [dbo].[Split]
( @cDelimiter varchar(5)
, @cCSV varchar(250)
, @cNullEmpty varchar(250) = NULL
)
RETURNS @Column TABLE
( CSV varchar(250)
)
AS
BEGIN
DECLARE @nIndex int
DECLARE @cValue varchar(250)
SET @nIndex = CHARINDEX(@cDelimiter,@cCSV,0)
IF @nIndex = 0
BEGIN
SET @cValue = @cCSV
IF @cValue = '' AND @cNullEmpty IS NULL
BEGIN
SET @cValue = NULL
END
IF @cValue = '' AND @cNullEmpty IS NOT NULL
BEGIN
SET @cValue = @cNullEmpty
END
INSERT INTO
@Column
SELECT @cValue
SET @cCSV = ''
END
WHILE LEN(@cCSV) > 0
BEGIN
SET @cValue = LEFT(@cCSV,@nIndex - 1)
IF @cValue = '' AND @cNullEmpty IS NULL
BEGIN
SET @cValue = NULL
END
IF @cValue = '' AND @cNullEmpty IS NOT NULL
BEGIN
SET @cValue = @cNullEmpty
END
INSERT
INTO @Column
SELECT @cValue
SET @cCSV = RIGHT(@cCSV,LEN(@cCSV) - @nIndex)
SET @nIndex = CHARINDEX(@cDelimiter,@cCSV,0)
IF @nIndex = 0
BEGIN
SET @cValue = @cCSV
IF @cValue = '' AND @cNullEmpty IS NULL
BEGIN
SET @cValue = NULL
END
IF @cValue = '' AND @cNullEmpty IS NOT NULL
BEGIN
SET @cValue = @cNullEmpty
END
INSERT
INTO @Column
SELECT @cValue
SET @cCSV = ''
END
END
RETURN
END
CREATE PROCEDURE [dbo].[GetPermutation]
(
@nSet numeric
, @nSubSet numeric = null
)
AS
DECLARE @nPermutation numeric
DECLARE @nCombination numeric
DECLARE @nComboID numeric
DECLARE @nComboLevel int
DECLARE @nPrevComboLevel int
DECLARE @nComboLevelPermutation numeric
IF @nSubSet IS NULL
BEGIN
SET @nCombination = @nSet
END
ELSE
BEGIN
SET @nCombination = @nSubSet
END
SET @nComboLevel = 2
SET @nComboID = @nSet + 1
SELECT @nPermutation = dbo.ComputePermutation(@nSet,@nCombination)
CREATE TABLE #Result
(
TotalPermutation numeric
, ComboLevel int
, ComboLevelPermutation numeric
, ComboLevelID int
, ComboID numeric
, RefKey varchar(500)
, RefValueIDPair varchar(500)
, RefValuePair varchar(500)
, RefValueID numeric
, RefValue numeric
, RefValueSum numeric
)
SELECT @nPermutation AS TotalPermutation
, 1 AS ComboLevel
, 1 AS ComboLevelPermutation
, 1 AS ComboLevelID
, IDENTITY(int,1,1) AS ComboID
, CONVERT(varchar,RefValueID) + ':' + CONVERT(varchar,RefValue) AS RefKey
, CONVERT(varchar,RefValueID) AS RefValueIDPair
, CONVERT(varchar,RefValueID) + ':' + CONVERT(varchar,RefValue) AS RefValuePair
, CONVERT(varchar,RefValueID) AS RefValueID
, RefValue
, RefValue AS RefValueSum
INTO #Initial
FROM RefValues
ORDER BY
RefValue
, RefValueID
DELETE
FROM #Initial
WHERE ComboID > @nSet
INSERT
INTO #Result
SELECT *
FROM #Initial
ORDER BY
RefValue
, RefValueID
WHILE @nComboLevel <= @nCombination
BEGIN
SET @nPrevComboLevel = @nComboLevel - 1
SELECT @nComboLevelPermutation = dbo.ComputePermutation(@nSet,@nComboLevel) - dbo.ComputePermutation(@nSet,@nPrevComboLevel)
DECLARE @cCurrentRefKey varchar(500)
DECLARE @nComboLevelID int
DECLARE @nSortCurrentComboID int
DECLARE RefKey_Cursor CURSOR FAST_FORWARD FOR
SELECT DISTINCT
RefKey
, ComboID
FROM #Result
WHERE ComboLevel = @nPrevComboLevel
ORDER BY
ComboID
OPEN RefKey_Cursor
FETCH NEXT
FROM RefKey_Cursor
INTO @cCurrentRefKey
, @nSortCurrentComboID
SELECT *
INTO #TempResult
FROM #Initial
ORDER BY
ComboID
SET @nComboLevelID = 1
WHILE @@FETCH_STATUS = 0
BEGIN
DECLARE @cComboRefKey varchar(500)
DECLARE @nSortComboID int
DECLARE Combo_Cursor CURSOR FAST_FORWARD FOR
SELECT DISTINCT
RefKey
, ComboID
FROM #TempResult
WHERE RefKey NOT IN (
SELECT CSV
FROM Split(',', @cCurrentRefKey, NULL)
)
ORDER BY
ComboID
OPEN Combo_Cursor
FETCH NEXT
FROM Combo_Cursor
INTO @cComboRefKey
, @nSortComboID
WHILE @@FETCH_STATUS = 0
BEGIN
DECLARE @cMaxCurrentValue numeric
DECLARE @cMaxComboValue numeric
DECLARE @nRefValueCurrentSum numeric
DECLARE @nRefValueComboSum numeric
DECLARE @nRefValueSum numeric
SELECT @cMaxCurrentValue = MAX(ComboID)
, @nRefValueCurrentSum = SUM(RefValue)
FROM #Initial
WHERE RefKey IN (
SELECT CSV
FROM Split(',', @cCurrentRefKey, NULL)
)
SELECT @cMaxComboValue = MAX(ComboID)
, @nRefValueComboSum = SUM(RefValue)
FROM #Initial
WHERE RefKey IN (
SELECT CSV
FROM Split(',', @cComboRefKey, NULL)
)
SET @nRefValueSum = @nRefValueCurrentSum + @nRefValueComboSum
IF @cMaxCurrentValue < @cMaxComboValue
BEGIN
SELECT @nPermutation AS TotalPermutation
, @nComboLevel AS ComboLevel
, @nComboLevelPermutation AS ComboLevelPermutation
, @nComboLevelID AS ComboLevelID
, @nComboID + 0 AS ComboID
, @cCurrentRefKey + ',' + @cComboRefKey AS RefKey
, RefValueIDPair
, RefValuePair
, RefValueID
, RefValue
, @nRefValueSum AS RefValueSum
INTO #ComboLevelResult
FROM #Initial
WHERE RefKey IN (
SELECT CSV
FROM Split(',', @cCurrentRefKey, NULL)
) OR
RefKey IN (
SELECT CSV
FROM Split(',', @cComboRefKey, NULL)
)
INSERT
INTO #Result
SELECT *
FROM #ComboLevelResult
ORDER BY
ComboID
, RefValue
, RefValueID
SET @nComboID = @nComboID + 1
SET @nComboLevelID = @nComboLevelID + 1
DROP
TABLE #ComboLevelResult
END
FETCH NEXT
FROM Combo_Cursor
INTO @cComboRefKey
, @nSortComboID
END
CLOSE Combo_Cursor
DEALLOCATE Combo_Cursor
DELETE
FROM #TempResult
WHERE RefKey = @cCurrentRefKey
FETCH NEXT
FROM RefKey_Cursor
INTO @cCurrentRefKey
, @nSortCurrentComboID
END
DROP
TABLE #TempResult
CLOSE RefKey_Cursor
DEALLOCATE RefKey_Cursor
SET @nComboLevel = @nComboLevel + 1
END
SELECT *
FROM #Result
ORDER BY
ComboID
DROP
TABLE #Result
DROP
TABLE #Initial
7. create a simple SP para sa problem natin,
CREATE PROCEDURE [dbo].[GetPermutationWithSum]
(
@nSets numeric
, @nSubSets numeric
, @nFindSum numeric = NULL
)
AS
CREATE TABLE #Result
(
TotalPermutation numeric
, ComboLevel int
, ComboLevelPermutation numeric
, ComboLevelID int
, ComboID numeric
, RefKey varchar(500)
, RefValueIDPair varchar(500)
, RefValuePair varchar(500)
, RefValueID numeric
, RefValue numeric
, RefValueSum numeric
)
INSERT
INTO #Result
EXEC GetPermutation @nSets, @nSubSets
SELECT ComboID
, RefValueID
, RefValue
FROM #Result
WHERE RefValueSum = (CASE WHEN @nFindSum IS NULL THEN RefValueSum ELSE @nFindSum END)
DROP
TABLE #Result
ayan hehehe pa test na lang master gg kung pasado ako! ![Geeked [8-|]](/cs/emoticons/emotion-15.gif)
hehehe uwi na ko gutom na ako! hehehhe