Aggregate Query question
-
nice information
-
Apology accepted!
Still no joy on hitting the optimal solution though. It seems I'm short by one doublet and one triplet. My current results are:
1. 15 doublets (30 districts)
2. 10 triplets (30 districts)
3. 1 singlet district (48) that already fits the population requirement
4. 5 stray districts
Here are the sets:
-- First the special districts you described
[2,47,58];[3,52];[6,13];[9,26];[35,63];[48];
-- Now for the 15 doublets
[8,25];[36,40];[11,64];[27,62];[28,59];[43,57];[23,32];[31,46];[1,12];[42,65];[10,45];[10,45];
-- And the 10 triplets
[22,49,50];[7,14,24];[15,19,37];[5,56,61];[21,30,41];[4,38,54];[17,18,53];[20,29,39];[16,34,44];
-- Finally, the 5 strays
[33];[51];[55];[60];[66]
So I suppose you'll want to know how I achieved such speed so posting of some code is in order. I'll explain as I go along and there are some comments in the code along the way with further explanation.
First we'll create a new districts table, and populate it with valid doublets, triplets and that one special singlet that fits the population profile.
CREATE TABLE NewDistricts
(n INT, d1 INT NOT NULL, d2 INT NOT NULL, d3 INT NOT NULL, dall VARCHAR(320), [Population] INT, PF INT)
ALTER TABLE NewDistricts
ADD PRIMARY KEY (d1, d2, d3)
GO
SET STATISTICS TIME ON
;WITH Doubles AS (
-- This CTE creates (from the Map) all possible combined districts with their populations
SELECT m.district, neighbor, d1=m.district, n1=neighbor
,[population]=SUM([population])
FROM Map m
INNER JOIN Sweden s
ON m.district = s.district or m.neighbor = s.district
GROUP BY m.district, neighbor),
Combine2and3 ( n, d1, d2, d3, dall, [Population]) AS (
-- This recursive CTE (one execution only of the recursive leg) combines the two/three
-- district combinations
SELECT 2, district, neighbor, 0
,CAST(d1 AS VARCHAR(8000)) + ',' + CAST(n1 AS VARCHAR(8000))
,[population]
FROM Doubles
WHERE population <= 6100
UNION ALL
SELECT 1 + n.n, y.d1, y.d2, y.d3
,CASE WHEN d < n.d1
THEN CAST(d AS VARCHAR(8000))+ ',' + CAST(n.dall AS VARCHAR(8000))
WHEN d > n.d2
THEN CAST(n.dall AS VARCHAR(8000)) + ',' + CAST(d AS VARCHAR(8000))
ELSE CAST(n.d1 AS VARCHAR(8000)) + ',' + CAST(d AS VARCHAR(8000)) + ',' + CAST(n.d2 AS VARCHAR(8000))
END
,n.[population] + s.[population]
FROM Combine2and3 n
INNER JOIN Doubles d ON (d.d1 IN (n.d1, n.d2) or d.n1 IN (n.d1, n.d2))
CROSS APPLY (
SELECT CASE WHEN d.d1 IN (n.d1, n.d2) THEN d.n1 ELSE d.d1 END) x(d)
INNER JOIN Sweden s ON s.district = d
-- To support later steps, we'll keep the districts sorted within the tuple
CROSS APPLY (
SELECT d1=CASE WHEN d < n.d1 THEN d WHEN d > d2 THEN n.d1 ELSE n.d1 END
,d2=CASE WHEN d < n.d1 THEN n.d1 WHEN d > d2 THEN n.d2 ELSE d END
,d3=CASE WHEN d < n.d1 THEN n.d2 WHEN d > d2 THEN d ELSE n.d2 END) y
WHERE n < 3 AND y.d1 <> y.d2 AND y.d2 <> y.d3
),
NewDistricts AS (
-- Finally NewDistricts converts the above to a unique set of (132) doublets and triplets
-- for use later. Up through here, all of these steps together are quite fast.
SELECT n, d1, d2, d3, dall, [population]
FROM (
SELECT n, d1, d2, d3, dall='[' + dall + ']', [population]
,rn=ROW_NUMBER() OVER (PARTITION BY n, d1, d2, d3 ORDER BY (SELECT NULL))
FROM Combine2and3
WHERE [population] BETWEEN 5900 AND 6100) x
WHERE rn=1),
CountByOccurrence AS (
SELECT d, [Count], Doublets, Triplets
FROM (
SELECT d, [Count]=SUM([Count]), Doublets=SUM(Doublets), Triplets=SUM(Triplets)
FROM NewDistricts
CROSS APPLY (VALUES (d1, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
,(d2, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
,(d3, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
) x(d, [Count], Doublets, Triplets)
WHERE d <> 0
GROUP BY d) x),
SpecialDistricts AS (
-- Special districts are those that don't exist in the doublets and triplets (only district=48)
SELECT d1, [population], dall='[' + CAST(d1 AS VARCHAR) + ']'
FROM (
SELECT d1=district FROM Sweden EXCEPT
SELECT d1
FROM (
SELECT d1 FROM NewDistricts
UNION ALL SELECT d2 FROM NewDistricts
UNION ALL SELECT d3 FROM NewDistricts) a
) b
INNER JOIN Sweden ON d1=district)
INSERT INTO dbo.NewDistricts
SELECT n, d1, d2, d3, dall, [population], PF
FROM (
SELECT n, d1, d2, d3, dall, [population]
,PF=c1.[Count] + c2.[Count] + ISNULL(c3.[Count], 0) -- Packing factor
FROM NewDistricts
LEFT JOIN CountByOccurrence c1 ON c1.d=d1
LEFT JOIN CountByOccurrence c2 ON c2.d=d2
LEFT JOIN CountByOccurrence c3 ON c3.d=d3
) a
UNION ALL
SELECT 1, d1, 0, 0, dall, [population], 1
FROM SpecialDistricts
-- Now mark those NewDistricts that contain a district with a single occurrence within the n-Tuple
;WITH CountByOccurrence AS (
SELECT d, [Count], Doublets, Triplets
FROM (
SELECT d, [Count]=SUM([Count]), Doublets=SUM(Doublets), Triplets=SUM(Triplets)
FROM NewDistricts
CROSS APPLY (VALUES (d1, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
,(d2, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
,(d3, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
) x(d, [Count], Doublets, Triplets)
WHERE d <> 0
GROUP BY d) x)
UPDATE nd
SET PF=0
FROM dbo.NewDistricts nd
INNER JOIN (
SELECT n, d1, d2, d3, a=a.[Count], b=ISNULL(b.[Count], 0), c=ISNULL(c.[Count], 0)
FROM NewDistricts
LEFT OUTER JOIN CountByOccurrence a ON a.d=d1
LEFT OUTER JOIN CountByOccurrence b ON b.d=d2
LEFT OUTER JOIN CountByOccurrence c ON c.d=d3
WHERE a.[Count]=1 OR ISNULL(b.[Count], 0)=1 OR ISNULL(c.[Count], 0)=1
) a ON nd.d1 = a.d1 AND nd.d2 = a.d2 AND nd.d3 = nd.d3
SET STATISTICS TIME OFF
SELECT * FROM NewDistricts ORDER BY PF, d1, d2, d3
This should run in about a minute and a half, mostly because of my ham-handed approach to calculating PF (my packing factor). Certainly there's probably a faster way to do this, I'm just not into optimizing that yet as we still have bigger fish to fry.
The packing factor establishes the order that we'll try "packing" our doublets and triplets into the final solution. The final SELECT above lists the NewDistricts in that order. I believe that by careful manipulation of the PF ordering, the optimal solution can be attained.
Now for the really fun part!
To build the final solution code, we start with a preamble that combines our 12 "special districts" that I've marked with a PF=0 into our starting array consisting of these fields:
n=Number of combined districts
np=Number of doublets
nt=Number of triplets
population is self evident
dall=The string of combined singlets, doublets and triplets I posted above.
d1, d2, ... d12=The first 12 districts that must participate and can only do so through the special district combinations
SET STATISTICS TIME ON
;WITH BaseDistricts AS (
-- Create a base of districts to start with. Each of the singlet (1), doublet (4) and triplet (1)
-- NewDistricts contain at least one district that appears in no other doublet or triplet.
SELECT d1=[1], d2=[2], d3=[3], d4=[4], d5=[5], d6=[6]
,d7=[7], d8=[8], d9=[9], d10=[10], d11=[11], d12=[12]
,dall, [population]
FROM (
SELECT d, n1=ROW_NUMBER() OVER (ORDER BY d)
FROM dbo.NewDistricts nd
CROSS APPLY (VALUES (d1), (d2), (d3)) b(d)
WHERE PF = 0 AND d<>0
) a
PIVOT (MAX(d) FOR n1 IN ([1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12])) pt
CROSS APPLY (
SELECT dall=STUFF((
SELECT ';' + dall FROM dbo.NewDistricts WHERE PF = 0
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 1, '')
,[population]=SUM([population])
FROM dbo.NewDistricts
WHERE PF = 0) a
)
SELECT
-- n = Number of combined districts
n=12
-- np = Number of combined doublets
,np=4
-- nt = Number of combined triplets
,nt=1
,[population]=base.[population]
,dall=base.dall
,d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12 -- From Base
FROM BaseDistricts base
SET STATISTICS TIME OFF
Not that I'm particularly proud of the above either. I'm no pivot expert so there's probably a more efficient way to do it. All I can say is that I finally got it working and it ran fast enough that I wasn't inclined to try to optimize it.
Next, we'll attempt to CROSS APPLY each remaining NewDistrict (where PF<>0) in the order established above. Unfortunately, this approach requires trying one at a time:
1) If the CROSS APPLY returns no rows, discard (fail) that new district
2) If the CROSS APPLY returns a row, keep that new district and proceed to test the next ones
This is a slow and arduous process! But it is quite repetitive. And in repetition there is the potential for automation (more on that later).
In the following code, I've captured all the successful CROSS APPLYs into the CTE named CombineNewDistricts and then added a little bit of extra to add in our stray districts.
SET STATISTICS TIME ON
;WITH BaseDistricts AS (
-- Create a base of districts to start with. Each of the singlet (1), doublet (4) and triplet (1)
-- NewDistricts contain at least one district that appears in no other doublet or triplet.
SELECT d1=[1], d2=[2], d3=[3], d4=[4], d5=[5], d6=[6]
,d7=[7], d8=[8], d9=[9], d10=[10], d11=[11], d12=[12]
,dall, [population]
FROM (
SELECT d, n1=ROW_NUMBER() OVER (ORDER BY d)
FROM dbo.NewDistricts nd
CROSS APPLY (VALUES (d1), (d2), (d3)) b(d)
WHERE PF = 0 AND d<>0
) a
PIVOT (MAX(d) FOR n1 IN ([1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12])) pt
CROSS APPLY (
SELECT dall=STUFF((
SELECT ';' + dall FROM dbo.NewDistricts WHERE PF = 0
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 1, '')
,[population]=SUM([population])
FROM dbo.NewDistricts
WHERE PF = 0) a
),
CombineNewDistricts AS (
SELECT
-- n = Number of combined districts
n=12+2+2+2+2+2+2+2+2+2+2+2+3+3+3+3+3+3+3+3
-- np = Number of combined doublets
,np=4+1+1+1+1+1+1+1+1+1+1+1
-- nt = Number of combined triplets
,nt=1+1+1+1+1+1+1+1+1+1
,[population]=base.[population] + a.[population] + b.[population] + c.[population] +
d.[population] + e.[population] + f.[population] + g.[population] + h.[population] +
i.[population] + j.[population] + k.[population] + l.[population] + m.[population] +
n.[population] + o.[population] + p.[population] + q.[population] + r.[population] +
s.[population] + t.[population]
,dall=base.dall + ';' + a.dall + ';' + b.dall + ';' + c.dall + ';' + d.dall + ';' + e.dall + ';' +
f.dall + ';' + g.dall + ';' + h.dall + ';' + i.dall + ';' + j.dall + ';' + k.dall + ';' +
k.dall + ';' + l.dall + ';' + m.dall + ';' + n.dall + ';' + o.dall + ';' + p.dall + ';' +
q.dall + ';' + r.dall + ';' + s.dall + ';' + t.dall
,d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12 -- From Base
,d13, d14 -- From a (doublet)
,d15, d16 -- From b (doublet)
,d17, d18 -- From c (doublet)
,d19, d20 -- From d (doublet)
,d21, d22 -- From e (doublet)
,d23, d24 -- From f (doublet)
,d25, d26 -- From g (doublet)
,d27, d28 -- From h (doublet)
,d29, d30 -- From i (doublet)
,d31, d32 -- From j (doublet)
,d33, d34 -- From k (doublet)
,d35, d36, d37 -- From l (triplet)
,d38, d39, d40 -- From m (triplet)
,d41, d42, d43 -- From n (triplet)
,d44, d45, d46 -- From o (triplet)
,d47, d48, d49 -- From p (triplet)
,d50, d51, d52 -- From q (triplet)
,d53, d54, d55 -- From r (triplet)
,d56, d57, d58 -- From s (triplet)
,d59, d60, d61 -- From t (triplet)
FROM BaseDistricts base
-- Try: [6,55] Fail (no rows returned)
-- Try: [8,25] Success (at least one row returned)
CROSS APPLY (
SELECT d13=d1, d14=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 8 AND d2 = 25 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12)) a
-- Try: [8,66] Fail
-- Try: [25,55] Fail
-- Try: [36,40] Success!
CROSS APPLY (
SELECT d15=d1, d16=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 36 AND d2 = 40 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14)) b
-- Try: [40,66] Fail
-- Try: [11,64] Success!
CROSS APPLY (
SELECT d17=d1, d18=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 11 AND d2 = 64 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16)) c
-- Try: [27,62] Success!
CROSS APPLY (
SELECT d19=d1, d20=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 27 AND d2 = 62 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18)) d
-- Try: [28,59] Success!
CROSS APPLY (
SELECT d21=d1, d22=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 28 AND d2 = 59 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20)) e
-- Try: [31,36] Fail
-- Try: [31,62] Fail
-- Try: [43,59] Fail
-- Try: [11,63] Fail
-- Try: [27,57] Fail
-- Try: [43,57] Success!
CROSS APPLY (
SELECT d23=d1, d24=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 43 AND d2 = 57 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22)) f
-- Try: [1,28] Fail
-- Try: [10,57] Fail
-- Try: [11,65] Fail
-- Try: [23,32] Success!
CROSS APPLY (
SELECT d25=d1, d26=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 23 AND d2 = 32 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24)) g
-- Try: [27,46] Fail
-- Try: [31,46] Success!
CROSS APPLY (
SELECT d27=d1, d28=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 31 AND d2 = 46 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26)) h
-- Try: [42,64] Fail
-- Try: [63,65] Fail
-- Try: [1,32] Fail
-- Try: [10,46] Fail
-- Try: [12,28] Fail
-- Try: [12,43] Fail
-- Try: [23,42] Fail
-- Try: [32,65] Fail
-- Try: [1,12] Success!
CROSS APPLY (
SELECT d29=d1, d30=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 1 AND d2 = 12 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28)) i
-- Try: [10,12] Fail
-- Try: [23,45] Fail
-- Try: [32,42] Fail
-- Try: [42,65] Success!
CROSS APPLY (
SELECT d31=d1, d32=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 42 AND d2 = 65 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30)) j
-- Try: [1,45] Fail
-- Try: [10,45] Success!
CROSS APPLY (
SELECT d33=d1, d34=d2, dall, [population]
FROM dbo.NewDistricts
WHERE n = 2 AND d1 = 10 AND d2 = 45 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32)) k
-- Try: [45,46] Fail
-- Try: [12,45] Fail
--CROSS APPLY (
-- SELECT d35=d1, d36=d2, dall, [population]
-- FROM dbo.NewDistricts
-- WHERE n = 2 AND d1 = 12 AND d2 = 45 AND
-- d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34) AND
-- d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34)) l
--
-- Try: [22,49,50] Success!
CROSS APPLY (
SELECT d35=d1, d36=d2, d37=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 22 AND d2 = 49 AND d3 = 50 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34)) l
-- Try: [42,45] Fail
--CROSS APPLY (
-- SELECT d38=d1, d39=d2, dall, [population]
-- FROM dbo.NewDistricts
-- WHERE n = 2 AND d1 = 42 AND d2 = 45 AND
-- d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37) AND
-- d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37)) m
-- Try: [2,5,47] Fail
-- Try: [7,14,24] Success!
CROSS APPLY (
SELECT d38=d1, d39=d2, d40=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 7 AND d2 = 14 AND d3 = 24 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37)) m
-- Try: [2,5,56] Fail
-- Try: [7,14,56] Fail
-- Try: [7,24,61] Fail
-- Try: [15,19,37] Success!
CROSS APPLY (
SELECT d41=d1, d42=d2, d43=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 15 AND d2 = 19 AND d3 = 37 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40)) n
-- Try: [2,5,61] Fail
-- Try: [5,14,56] Fail
-- Try: [5,24,61] Fail
-- Try: [7,14,61] Fail
-- Try: [14,24,61] Fail
-- Try: [22,38,49] Fail
-- Try: [5,56,61] Success!
CROSS APPLY (
SELECT d44=d1, d45=d2, d46=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 5 AND d2 = 56 AND d3 = 61 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43)) o
-- Try: [14,56,61] Fail
-- Try: [22,38,50] Fail
-- Try: [5,14,61] Fail
-- Try: [15,30,37] Fail
-- Try: [19,30,37] Fail
-- Try: [21,30,41] Success!
CROSS APPLY (
SELECT d47=d1, d48=d2, d49=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 21 AND d2 = 30 AND d3 = 41 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46)) p
-- Try: [4,38,50] Fail
-- Try: [4,22,38] Fail
-- Try: [21,33,41] Fail
-- Try: [4,38,54] Success!
CROSS APPLY (
SELECT d50=d1, d51=d2, d52=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 4 AND d2 = 38 AND d3 = 54 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49)) q
-- Try: [30,37,41] Fail
-- Try: [30,33,41] Fail
-- Try: [4,16,54] Fail
-- Try: [34,38,50] Fail
-- Try: [15,37,51] Fail
-- Try: [17,21,33] Fail
-- Try: [19,37,51] Fail
-- Try: [22,34,38] Fail
-- Try: [4,34,54] Fail
-- Try: [21,41,51] Fail
-- Try: [16,20,54] Fail
-- Try: [17,18,53] Success!
CROSS APPLY (
SELECT d53=d1, d54=d2, d55=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 17 AND d2 = 18 AND d3 = 53 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52)) r
-- Try: [17,33,53] Fail
-- Try: [16,44,54] Fail
-- Try: [21,33,51] Fail
-- Try: [4,16,38] Fail
-- Try: [16,34,54] Fail
-- Try: [17,33,41] Fail
-- Try: [4,34,38] Fail
-- Try: [30,37,51] Fail
-- Try: [30,41,51] Fail
-- Try: [17,18,33] Fail
-- Try: [18,53,60] Fail
-- Try: [37,41,51] Fail
-- Try: [39,53,60] Fail
-- Try: [4,16,20] Fail
-- Try: [18,30,51] Fail
-- Try: [20,29,39] Success!
CROSS APPLY (
SELECT d56=d1, d57=d2, d58=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 20 AND d2 = 29 AND d3 = 39 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55)) s
-- Try: [30,33,51] Fail
-- Try: [4,16,44] Fail
-- Try: [16,20,39] Fail
-- Try: [18,37,51] Fail
-- Try: [18,41,51] Fail
-- Try: [20,39,44] Fail
-- Try: [29,39,44] Fail
-- Try: [33,37,51] Fail
-- Try: [33,41,51] Fail
-- Try: [4,29,34] Fail
-- Try: [16,39,44] Fail
-- Try: [20,53,60] Fail
-- Try: [29,34,38] Fail
-- Try: [29,53,60] Fail
-- Try: [4,16,34] Fail
-- Try: [4,34,44] Fail
-- Try: [16,34,38] Fail
-- Try: [17,51,53] Fail
-- Try: [18,33,51] Fail
-- Try: [29,34,39] Fail
-- Try: [34,38,44] Fail
-- Try: [17,53,60] Fail
-- Try: [18,39,60] Fail
-- Try: [20,29,44] Fail
-- Try: [34,39,44] Fail
-- Try: [16,20,44] Fail
-- Try: [16,29,44] Fail
-- Try: [17,30,51] Fail
-- Try: [17,37,51] Fail
-- Try: [17,41,51] Fail
-- Try: [16,20,34] Fail
-- Try: [16,29,34] Fail
-- Try: [18,20,60] Fail
-- Try: [18,29,60] Fail
-- Try: [20,34,44] Fail
-- Try: [20,39,60] Fail
-- Try: [29,34,44] Fail
-- Try: [29,39,60] Fail
-- Try: [16,34,44] Success!
CROSS APPLY (
SELECT d59=d1, d60=d2, d61=d3, dall, [population]
FROM dbo.NewDistricts
WHERE n = 3 AND d1 = 16 AND d2 = 34 AND d3 = 44 AND
d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58) AND
d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58) AND
d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58)) t
-- Try: [17,18,51] Fail
-- Try: [17,33,51] Fail
-- Try: [39,44,60] Fail
-- Try: [17,18,60] Fail
-- Try: [17,33,60] Fail
-- Try: [17,39,60] Fail
-- Try: [20,29,60] Fail
-- Try: [16,20,60] Fail
-- Try: [20,44,60] Fail
-- Try: [29,44,60] Fail
-- Try: [17,20,60] Fail
-- Try: [17,29,60] Fail
-- Try: [18,51,60] Fail
-- Try: [29,34,60] Fail
-- Try: [17,51,60] Fail
--CROSS APPLY (
-- SELECT d62=d1, d63=d2, d64=d3, dall, [population]
-- FROM dbo.NewDistricts
-- WHERE n = 3 AND d1 = 17 AND d2 = 51 AND d3 = 60 AND
-- d1 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58,d59,d60,d61) AND
-- d2 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58,d59,d60,d61) AND
-- d3 NOT IN (base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15,d16,d17,d18,d19,d20,d21,d22,d23,d24,d25,d26,d27,d28,d29,d30,d31,d32,d33,d34,d35,d36,d37,d38,d39,d40,d41,d42,d43,d44,d45,d46,d47,d48,d49,d50,d51,d52,d53,d54,d55,d56,d57,d58,d59,d60,d61)) u
)
SELECT n=n+5, np, nt
,[population]=a.[population] + b.[population]
,dall = a.dall + ';[' + CAST(d62 AS VARCHAR) + '];[' + CAST(d63 AS VARCHAR) + '];[' +
CAST(d64 AS VARCHAR) + + '];[' + CAST(d65 AS VARCHAR) + '];[' + CAST(d66 AS VARCHAR) + ']'
FROM CombineNewDistricts a
-- Now add in the districts missed above (there are 5 singlets)
CROSS APPLY (
SELECT d62=SUM([1]), d63=SUM([2]), d64=SUM([3]), d65=SUM([4]), d66=SUM([5])
,[population]=SUM(pt.[population])
FROM (
SELECT District, ElimDist, a.[population]
,n=ROW_NUMBER() OVER (PARTITION BY ElimDist ORDER BY District)
FROM Sweden a
CROSS APPLY (
SELECT CASE
WHEN district IN (d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d11, d12, d13, d14, d15, d16, d17
,d18, d19, d20, d21, d22, d23, d24, d25, d26, d27, d28, d29, d30, d31, d32, d33, d34
,d35, d36, d37, d38, d39, d40, d41, d42, d43, d44, d45, d46, d47, d48, d49, d50, d51, d52
,d53, d54, d55, d56, d57, d58, d59, d60, d61)
THEN 0 ELSE 1 END) b(ElimDist)
WHERE ElimDist = 1
) d
PIVOT (MAX(district)
FOR n IN ([1], [2], [3], [4], [5])) pt
) b
SET STATISTICS TIME OFF
Not sure how long this would take to run the first time, but with a little training the optimizer makes short work of it and it runs in the blink of an eye generating the final result I posted above.
Now that is the mother of all cascaded CROSS APPLYs! I suspect, however that you'll call my "try/fail/success" approach sort of a cheat because it doesn't capture the additional time doing a try that fails. So be it.
As I noted, since the manual process I used is repetitous, I believe it can be automated with some diabolically complicated dynamic SQL. Then, we can modify the PF column (and add some additional columns) to provide the ordering for the "try NewDistrict" processing, iterating through the order columns, thus whacking out multiple solutions each time it is run.
I'm going to work on that over the weekend.
I love this challenge!
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
I haven't walked through the code yet, but...
[33,51,60] - is a triple
[55, 66] - is a double
Triples - I only count 9 in your list. Add the above (33,51,60) and it'll be 10 (correct).
Doubles - I think you just miscounted. I count 11 (the last double is repeated in your list), add the [55,66] and it's 12 (correct).
>>Love this challenge!
Yah, I'm a sucker for these from time to time. They're always a great learning experience, if they don't put me over the edge :w00t:
Dr. Les Cardwell, DCS-DSS
Enterprise Data Architect
Central Lincoln PUD -
Les Cardwell (7/5/2012)
I haven't walked through the code yet, but...[33,51,60] - is a triple
[55, 66] - is a double
Triples - I only count 9 in your list. Add the above (33,51,60) and it'll be 10 (correct).
Doubles - I think you just miscounted. I count 11 (the last double is repeated in your list), add the [55,66] and it's 12 (correct).
>>Love this challenge!
Yah, I'm a sucker for these from time to time. They're always a great learning experience, if they don't put me over the edge :w00t:
There was a minor error in my POC "mother of cascading CROSS APPLY" query that caused the doubling of [10,45]. Note that k.dall was included twice in the top SELECT of CombineNewDistricts. Corrected results:
[2,47,58];[3,52];[6,13];[9,26];[35,63];[48];
[8,25];[36,40];[11,64];[27,62];[28,59];[43,57];[23,32];[31,46];[1,12];[42,65];[10,45];
[22,49,50];[7,14,24];[15,19,37];[5,56,61];[21,30,41];[4,38,54];[17,18,53];[20,29,39];[16,34,44];
[33];[51];[55];[60];[66]
As to the doublet and triplet you identified missing from my results set, obviously great minds think alike! That is the next thing I was going to look for.
Since I spent some time on this last night, I'm on the cusp of what I hope will be the final solution.
Once again, stay tuned!
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
Les Cardwell (7/5/2012)
[33,51,60] - is a triple[55, 66] - is a double
I checked my NewDistricts table and these two aren't in it but they should be, so I need to go back and check my logic there to see why they weren't included.
The good news, is that I finished writing a Stored Procedure that is able to iterate through multiple, likely solution cases in the time it takes for a hummingbird to flap its wing!
I'll post the whole shootin' match after I figure out what's wrong with my NewDistricts generator posted earlier.
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
dwain.c (7/5/2012)
Les Cardwell (7/5/2012)
[33,51,60] - is a triple[55, 66] - is a double
I checked my NewDistricts table and these two aren't in it but they should be, so I need to go back and check my logic there to see why they weren't included.
The good news, is that I finished writing a Stored Procedure that is able to iterate through multiple, likely solution cases in the time it takes for a hummingbird to flap its wing!
I'll post the whole shootin' match after I figure out what's wrong with my NewDistricts generator posted earlier.
OK Les, now I think you're yanking my chain!
In order for [55,66] to be a valid double, there should be a Map entry for 55/60 (district/neighbor) but that doesn't exist in the data set you provided. In that general vicinity (SW2) I see these only:
INSERT INTO Map VALUES (52,53);
INSERT INTO Map VALUES (53,60);
INSERT INTO Map VALUES (55,61);
INSERT INTO Map VALUES (58,66);
INSERT INTO Map VALUES (63,65);
Also, for [33,51,60] to be a valid triple, I have 33/51 in the Map but I don't have either 33/60 or 51/60 to make the triple.
Here is what I have in that vicinity:
<snip>
INSERT INTO Map VALUES (32,65);
INSERT INTO Map VALUES (33,41);
INSERT INTO Map VALUES (33,51);
INSERT INTO Map VALUES (33,52);
INSERT INTO Map VALUES (34,38);
<snip>
INSERT INTO Map VALUES (48,64);
INSERT INTO Map VALUES (52,53);
Also, going back to Dr. Dobb's original map:
55 doesn't look close to 66, unless you would allow 25/66 but that's not in the map either, i.e., I'm not sure if 55/66 should be in the Map table.
Similar arguments apply the the triplet you said is there. I'm going to go back and review how you're creating those districts but something seems amiss here.
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
You're right. It's not in my set either...No clue, other than my mind is also on PTO perhaps :ermm:
AAR, just use the select code from SW6 to get valid sets of doubles or triples...
Doubles...
SELECT DISTINCT S1.district, S1.population
FROM Sweden AS S1, Sweden AS S2
WHERE (S1.district < S2.district
OR S1.district = 66 ) --to pick up the last district in doubles (!?)
AND EXISTS (
SELECT *
FROM Remaining AS R1
WHERER1.district3 = 0
ANDS1.district IN ( R1.district1, R1.district2 ) )
ORDER BY S1.district
--------
Triples (note I modified this from SW6 to use Remaining vs. Candidates to eliminate the outlier)...
SELECT DISTINCT S1.district, S1.population
FROM Sweden AS S1, Sweden AS S2
WHERES1.district < S2.district
AND EXISTS (
SELECT *
FROM Remaining AS R1
WHERER1.district3 > 0
ANDS1.district IN (R1.district1, R1.district2, R1.district3 ) )
ORDER BY S1.district
Dr. Les Cardwell, DCS-DSS
Enterprise Data Architect
Central Lincoln PUD -
Dwain,
Using your CTE, I've come up with a hybrid solution that shortens my initial code considerably. I'll test over the next day or so and post the findings. I also haven't done much with Pivot in the past, but think it might streamline it further. More experiments...
~Les
Dr. Les Cardwell, DCS-DSS
Enterprise Data Architect
Central Lincoln PUD -
Les Cardwell (7/6/2012)
You're right. It's not in my set either...No clue, other than my mind is also on PTO perhaps :ermm:Whew! That's a relief. Thought I'd missed an important assumption (again).
Didn't get much time to work on this over the weekend but I'm still planning to plug away. I did get some ideas...
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
OK. It's time for a checkpoint, if for no other reason that to get straight in my head what I've been doing.
First, I needed to convince myself of something that you probably already knew. That is, if a district participates in a doublet, it does not also participate in a triplet (and vice versa of course). That is confirmed by the following (which returns no rows):
SELECT d
FROM (SELECT d FROM NewDistricts CROSS APPLY (VALUES (d1), (d2)) a(d) WHERE n=2) a
INTERSECT
SELECT d
FROM (SELECT d FROM NewDistricts CROSS APPLY (VALUES (d1), (d2),(d3)) a(d) WHERE n=3) b
I mentioned to you last week that I had an idea on how to generate multiple solutions. In order to do this, we must make a change to the NewDistricts table. I've already given you the DDL to create that table including the PF (packing factor) column. Now we'll add a few columns that I'll explain in a minute.
ALTER TABLE dbo.NewDistricts ADD n1 INT
ALTER TABLE dbo.NewDistricts ADD n2 INT
ALTER TABLE dbo.NewDistricts ADD n3 INT
ALTER TABLE dbo.NewDistricts ADD n4 INT
ALTER TABLE dbo.NewDistricts ADD n5 INT
ALTER TABLE dbo.NewDistricts ADD n6 INT
ALTER TABLE dbo.NewDistricts ADD n7 INT
ALTER TABLE dbo.NewDistricts ADD n8 INT
ALTER TABLE dbo.NewDistricts ADD n9 INT
ALTER TABLE dbo.NewDistricts ADD n10 INT
My initial "mother of all cascading CROSS APPLY queries" was a useful exercise as it established the pattern for what is about to transpire. Recall the "TRY/FAIL/SUCCESS" approach? The first time through I did it manually completely based on the PF column that I have in my NewDistricts TABLE. The new n1, n2, ..., n10 columns we just added to NewDistricts will establish that order for performing the tries based on a packing factor, either the initial one I chose to set up or some other.
I am convinced that the PF, which establishes the order that doublets and triplets are packed into the solution is the key to eventually arriving at the optimal solution. I believe that solution to consist of 16 doublets and 11 triplets. I have achieved the former but the best I've been able to do so far on the triplets is 10. Below I show one of these.
Let's try populating the n columns in our NewDistricts table with the following:
-- Set the initial PF
;WITH CountByOccurrence AS (
SELECT d, [Count], Doublets, Triplets
FROM (
SELECT d, [Count]=SUM([Count]), Doublets=SUM(Doublets), Triplets=SUM(Triplets)
FROM dbo.NewDistricts
CROSS APPLY (VALUES (d1, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
,(d2, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
,(d3, 1, CASE WHEN n=2 THEN 1 ELSE 0 END, CASE WHEN n=3 THEN 1 ELSE 0 END)
) x(d, [Count], Doublets, Triplets)
WHERE d <> 0
GROUP BY d) x),
SpecialDistricts (d1, d2, d3) AS (
SELECT 48, 0, 0 UNION ALL SELECT 35, 63, 0 UNION ALL SELECT 9, 26, 0
UNION ALL SELECT 6, 13, 0 UNION ALL SELECT 3, 52, 0 UNION ALL SELECT 2, 47, 58)
UPDATE nd
SET PF=CASE WHEN sd.d1 IS NULL THEN a+b+c ELSE 0 END
FROM dbo.NewDistricts nd
LEFT OUTER JOIN SpecialDistricts sd ON sd.d1 = nd.d1 AND sd.d2 = nd.d2 AND sd.d3 = nd.d3
INNER JOIN (
SELECT n, d1, d2, d3, a=a.[Count], b=ISNULL(b.[Count], 0), c=ISNULL(c.[Count], 0)
FROM dbo.NewDistricts
LEFT OUTER JOIN CountByOccurrence a ON a.d=d1
LEFT OUTER JOIN CountByOccurrence b ON b.d=d2
LEFT OUTER JOIN CountByOccurrence c ON c.d=d3
) a ON nd.d1 = a.d1 AND nd.d2 = a.d2 AND nd.d3 = a.d3
-- Populate the sort columns for unused rows (i.e., where PF=0)
UPDATE dbo.NewDistricts
SET n1=0, n2=0, n3=0, n4=0, n5=0, n6=0, n7=0, n8=0, n9=0, n10=0
WHERE PF=0
-- Let's try to populate the packing order in our n1, n2, ..., n10 columns
-- Hold off on n2 because we'll populate that one by learning from prior solution
UPDATE a
SET n1=rn1, n3=rn3, n4=rn4, n5=rn5, n6=rn6, n7=rn7, n8=rn8, n9=rn9, n10=rn10
FROM dbo.NewDistricts a
INNER JOIN (
SELECT d1, d2, d3
-- Our baseline (as prior solution): Sort by Packing Factor
,rn1=ROW_NUMBER() OVER (ORDER BY PF, d1, d2, d3)
-- Some completely random sorts (in case we get lucky)
,rn3=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn4=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn5=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn6=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn7=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn8=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn9=ROW_NUMBER() OVER (ORDER BY NEWID())
,rn10=ROW_NUMBER() OVER (ORDER BY NEWID())
FROM dbo.NewDistricts
WHERE PF<>0) b
ON a.d1 = b.d1 AND a.d2 = b.d2 AND a.d3 = b.d3
;WITH Keepers (d1, d2, d3) AS (
SELECT 8, 66, 0 UNION ALL SELECT 25, 55, 0
UNION ALL SELECT 30, 37, 41 UNION ALL SELECT 17, 18, 52)
UPDATE a
SET PF=1
FROM dbo.NewDistricts a
INNER JOIN Keepers b ON a.d1 = b.d1 AND a.d2 = b.d2 AND a.d3 = b.d3
UPDATE a
SET n2=rn2
FROM dbo.NewDistricts a
INNER JOIN (
SELECT d1, d2, d3
-- Optimal solution for doublets but only nearly optimal for triplets
,rn2=ROW_NUMBER() OVER (ORDER BY n, PF, d1, d2, d3)
FROM dbo.NewDistricts
WHERE PF<>0) b
ON a.d1 = b.d1 AND a.d2 = b.d2 AND a.d3 = b.d3
We'll also need a Solutions table and a SP that generates the solution:
-- Create a table to store our solutions
CREATE TABLE dbo.Solutions
(SolutionID INT IDENTITY PRIMARY KEY, n INT, np INT, nt INT
,[Population] INT, [Solution] VARCHAR(320), SQL4Solution NVARCHAR(MAX))
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
-- =============================================
-- Author:Dwain Camps
-- Create date: 05-Jul-2012
-- Description:Dynamic method to resolve the Sweden re-districting problem.
-- =============================================
CREATE PROCEDURE [dbo].[GenerateSwedenRedistrictingSolutions]
@NoSolutions INT = 1
AS
BEGIN
SET NOCOUNT ON;
-- Declare some variables to use in building the Dynamic SQL
DECLARE @InitialCTE NVARCHAR(MAX)
,@CountOfn NVARCHAR(MAX) = 'n=12'
,@CountOfnp NVARCHAR(MAX) = 'np=4'
,@CountOfnt NVARCHAR(MAX) = 'nt=1'
,@Pop NVARCHAR(MAX) = 'population=base.[population]'
,@dall NVARCHAR(MAX) = 'dall=base.dall'
,@BaseDistricts NVARCHAR(MAX) = 'd1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12'
,@CADoublets NVARCHAR(MAX)
,@CATriplets NVARCHAR(MAX)
,@DistrictColumns NVARCHAR(MAX) = 'base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12'
,@SQL4Districts NVARCHAR(MAX) = ''
,@SQL2Keep NVARCHAR(MAX) = ''
,@SQL2Try NVARCHAR(MAX) = ''
,@SQL2Save NVARCHAR(MAX) = ''
,@WorkingCAs NVARCHAR(MAX) = ''
-- Declare some loop and counter variables
DECLARE @DerivedTabCounter INT = 1
,@SolutionCounter INT = 1
,@CurrentDistrict INT = 13
,@CurrentTryCounter INT = 1
-- Holders for districts read from NewDistricts
,@d1 INT
,@d2 INT
,@d3 INT
,@TotalNewDistricts INT
,@rc INT
,@Lastnp INT
,@Lastnt INT
,@Lastn INT
-- Junk (mostly): to dump the Try resuls so they don't get displayed
,@n INT
,@np INT
,@nt INT
,@da VARCHAR(320)
,@population INT
-- Loop for each potential solution in columns n1, n2, ... of NewDistricts
WHILE @SolutionCounter <= @NoSolutions
BEGIN
SELECT
@InitialCTE =
';WITH BaseDistricts AS (' +
' SELECT d1=[1], d2=[2], d3=[3], d4=[4], d5=[5], d6=[6] ' +
' ,d7=[7], d8=[8], d9=[9], d10=[10], d11=[11], d12=[12] ' +
' ,dall, [population] ' +
' FROM ( ' +
' SELECT d, n1=ROW_NUMBER() OVER (ORDER BY d) ' +
' FROM dbo.NewDistricts nd ' +
' CROSS APPLY (VALUES (d1), (d2), (d3)) b(d) ' +
' WHERE n' + CAST(@SolutionCounter AS VARCHAR) + '= 0 AND d<>0)a ' +
' PIVOT (MAX(d) FOR n1 IN ([1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12])) pt ' +
' CROSS APPLY ( ' +
' SELECT dall=STUFF(( ' +
' SELECT '';'' + dall FROM dbo.NewDistricts WHERE PF = 0 ' +
' FOR XML PATH(''''), TYPE).value(''.'', ''VARCHAR(MAX)''), 1, 1, '''') ' +
' ,[population]=SUM([population]) ' +
' FROM dbo.NewDistricts ' +
' WHERE n' + CAST(@SolutionCounter AS VARCHAR) + ' = 0) a) '
SELECT @TotalNewDistricts = COUNT(*)-6 FROM NewDistricts
PRINT 'Starting calculation of solution number: ' + CAST(@SolutionCounter AS VARCHAR) + ' ' +
CONVERT(VARCHAR(100),GETDATE(),121)
WHILE @CurrentTryCounter <= @TotalNewDistricts
BEGIN
-- SELECT the next NewDistrict to try
SELECT @SQL4Districts = 'SELECT @d1=d1, @d2=d2, @d3=d3 FROM NewDistricts WHERE n' +
CAST(@SolutionCounter AS VARCHAR) + '=@ctc'
EXEC sp_executesql @SQL4Districts
,@params=N'@ctc INT, @d1 INT OUTPUT, @d2 INT OUTPUT, @d3 INT OUTPUT'
,@ctc=@CurrentTryCounter, @d1=@d1 OUTPUT, @d2=@d2 OUTPUT, @d3=@d3 OUTPUT
SELECT -- Create the SQL for the cascading, correlated CROSS APPLYs
@CADoublets =
' CROSS APPLY (' +
'SELECT d' + CAST(@CurrentDistrict AS VARCHAR) + '=d1, d' +
CAST(@CurrentDistrict+1 AS VARCHAR) + '=d2, dall, [population] ' +
'FROM dbo.NewDistricts ' +
'WHERE n = 2 AND d1 = ' + CAST(@d1 AS VARCHAR) + ' AND d2 = ' +
CAST(@d2 AS VARCHAR) + ' AND ' +
' d1 NOT IN (' + @DistrictColumns + ') AND' +
' d2 NOT IN (' + @DistrictColumns + ')) a' + CAST(@DerivedTabCounter AS VARCHAR)
,@CATriplets =
' CROSS APPLY (' +
'SELECT d' + CAST(@CurrentDistrict AS VARCHAR) + '=d1, d' +
CAST(@CurrentDistrict+1 AS VARCHAR) + '=d2, d' +
CAST(@CurrentDistrict+2 AS VARCHAR) + '=d3, dall, [population] ' +
'FROM dbo.NewDistricts ' +
'WHERE n = 3 AND d1 = ' + CAST(@d1 AS VARCHAR) + ' AND d2 = ' +
CAST(@d2 AS VARCHAR) + ' AND d3 = ' + CAST(@d3 AS VARCHAR) + ' AND' +
' d1 NOT IN (' + @DistrictColumns + ') AND ' +
' d2 NOT IN (' + @DistrictColumns + ') AND ' +
' d3 NOT IN (' + @DistrictColumns + ')) a' + CAST(@DerivedTabCounter AS VARCHAR)
-- Build the base SQL to try
SELECT @SQL2Try = @InitialCTE + ' SELECT @' + @CountOfn + ',@' +
@CountOfnp + ',@' + @CountOfnt + ',@' +
@pop + ',@' + @dall + ' FROM BaseDistricts base ' + @WorkingCAs +
CASE WHEN @d3 = 0 THEN @CADoublets ELSE @CATriplets END
--IF @SolutionCounter > 1
--PRINT 'Trying ' + CASE WHEN @d3 = 0 THEN 'doublet' ELSE 'triplet' END + ': [' +
-- CAST(@d1 AS VARCHAR) + ',' + CAST(@d2 AS VARCHAR) +
-- CASE WHEN @d3 = 0 THEN ']' ELSE ',' + CAST(@d3 AS VARCHAR) + ']' END
EXEC sp_executesql @SQL2Try
,@params=N'@n INT OUTPUT, @np INT OUTPUT, @nt INT OUTPUT, @dall VARCHAR(320) OUTPUT, @population INT OUTPUT'
,@n=@n OUTPUT, @np=@np OUTPUT, @nt=@nt OUTPUT, @dall=@da OUTPUT, @population=@population OUTPUT
SELECT @rc=@@ROWCOUNT
--IF @SolutionCounter > 1
--PRINT 'Result: ' + CASE @rc WHEN 0 THEN 'Fail!' ELSE 'Success!' END + ' for try count: ' +
-- CAST(@CurrentTryCounter AS VARCHAR)
-- If row count above found a row, then we've got a good NewDistrict to add to our list
IF @rc <> 0 SELECT
@Lastn = @n + CASE WHEN @d3 = 0 THEN 2 ELSE 3 END
,@Lastnp = @np + CASE WHEN @d3 = 0 THEN 1 ELSE 0 END
,@Lastnt = @nt + CASE WHEN @d3 = 0 THEN 0 ELSE 1 END
,@WorkingCAs = @WorkingCAs + CASE WHEN @d3 = 0 THEN @CADoublets ELSE @CATriplets END
,@CountOfn = @CountOfn + CASE WHEN @d3 = 0 THEN '+2' ELSE '+3' END
,@CountOfnp = @CountOfnp + CASE WHEN @d3 = 0 THEN '+1' ELSE '+0' END
,@CountOfnt = @CountOfnt + CASE WHEN @d3 <> 0 THEN '+1' ELSE '+0' END
,@DistrictColumns = @DistrictColumns + ',d' + CAST(@CurrentDistrict AS VARCHAR) +
',d' + CAST(@CurrentDistrict+1 AS VARCHAR) +
CASE WHEN @d3 = 0 THEN '' ELSE ',d' + CAST(@CurrentDistrict+2 AS VARCHAR) END
,@BaseDistricts = @BaseDistricts + ',d' + CAST(@CurrentDistrict AS VARCHAR) +
',d' + CAST(@CurrentDistrict+1 AS VARCHAR) +
CASE WHEN @d3 = 0 THEN '' ELSE ',d' + CAST(@CurrentDistrict+2 AS VARCHAR) END
,@CurrentDistrict = @CurrentDistrict + CASE WHEN @d3 = 0 THEN 2 ELSE 3 END
,@Pop = @pop + '+a' + CAST(@DerivedTabCounter AS VARCHAR) + '.[Population]'
,@dall = @dall + '+'';''+a' + CAST(@DerivedTabCounter AS VARCHAR) + '.dall'
,@DerivedTabCounter = @DerivedTabCounter + 1
-- Let's give it another try shall we?
SELECT @CurrentTryCounter = @CurrentTryCounter + 1
END -- Of WHILE (try CROSS APPLYs)
-- Build the SQL to execute to save the solution
IF @Lastnp * 2 + @Lastnt * 3 = 65 -- No need for the fancy stuff (optimal solution)
BEGIN
-- First the SQL to save in the Solutions table
SELECT @SQL2Save = @InitialCTE + ' SELECT ' + @CountOfn + ',' +
@CountOfnp + ',' + @CountOfnt + ',' + @pop + ',' + @dall + ',' + @BaseDistricts +
' FROM BaseDistricts base ' + @WorkingCAs
-- Our SQL to execute is just the final query we constructed above (with an INSERT)
SELECT @SQL2Keep = @InitialCTE + ' INSERT INTO dbo.Solutions ' +
' SELECT ' + @CountOfn + ',' +
@CountOfnp + ',' + @CountOfnt + ',' + @pop + ',' + @dall + ',' + @BaseDistricts +
',SQL4Solution=N''' + REPLACE(@SQL2Save, '''', '''''') + '''' +
' FROM BaseDistricts base ' + @WorkingCAs
END
ELSE BEGIN
-- If not optimal solution, it's necessary to add a PIVOT to include the eliminated districts
-- First the SQL to save in the Solutions table
;WITH Tally (m) AS (
SELECT TOP (66-@Lastn) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM sys.all_columns),
SpecialVars AS (
SELECT m, Col4Pivot='[' + CAST(m AS VARCHAR) + ']'
,MissingDistrict='d' + CAST(@CurrentDistrict + m - 1 AS VARCHAR)
FROM Tally)
SELECT @SQL2Save = @InitialCTE + ', CombineNewDistricts AS ( SELECT ' +
@CountOfn + ',' +
@CountOfnp + ',' + @CountOfnt + ',' + @pop + ',' + @dall + ',' + @BaseDistricts +
' FROM BaseDistricts base ' + @WorkingCAs + ') ' +
' SELECT n=n+' + CAST(66-@Lastn AS VARCHAR) +
',np,nt,[population]=a.[population] + b.[population],dall = a.dall + '';' +
STUFF((
SELECT '''];['' + CAST(' + MissingDistrict + ' AS VARCHAR) +'
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 3, '') + ''']''' +
',' + @BaseDistricts +
( SELECT ',' + MissingDistrict
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)') +
' FROM CombineNewDistricts a CROSS APPLY ( SELECT ' +
STUFF((
SELECT ',' + MissingDistrict + '=SUM(' + Col4Pivot + ')'
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 1, '') + ', ' +
'[population]=SUM(pt.[population]) FROM (SELECT District, ElimDist, a.[population]' +
',n=ROW_NUMBER() OVER (PARTITION BY ElimDist ORDER BY District) FROM Sweden a ' +
'CROSS APPLY (SELECT CASE WHEN district IN (' + @BaseDistricts + ') ' +
'THEN 0 ELSE 1 END) b(ElimDist) WHERE ElimDist = 1) d PIVOT (MAX(district) FOR n IN (' +
STUFF((
SELECT ',' + Col4Pivot
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 1, '') +
')) pt) b'
-- Next is nearly the same as above except it INSERTs into Solutions TABLE
;WITH Tally (m) AS (
SELECT TOP (66-@Lastn) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM sys.all_columns),
SpecialVars AS (
SELECT m, Col4Pivot='[' + CAST(m AS VARCHAR) + ']'
,MissingDistrict='d' + CAST(@CurrentDistrict + m - 1 AS VARCHAR)
FROM Tally)
SELECT @SQL2Keep = @InitialCTE + ', CombineNewDistricts AS ( SELECT ' +
@CountOfn + ',' +
@CountOfnp + ',' + @CountOfnt + ',' + @pop + ',' + @dall + ',' + @BaseDistricts +
' FROM BaseDistricts base ' + @WorkingCAs + ') ' + 'INSERT INTO dbo.Solutions ' +
' SELECT n=n+' + CAST(66-@Lastn AS VARCHAR) +
',np,nt,[population]=a.[population] + b.[population],dall = a.dall + '';' +
STUFF((
SELECT '''];['' + CAST(' + MissingDistrict + ' AS VARCHAR) +'
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 3, '') + ''']''' +
',SQL4Solution=N''' + REPLACE(@SQL2Save, '''', '''''') + '''' +
' FROM CombineNewDistricts a CROSS APPLY ( SELECT ' +
STUFF((
SELECT ',' + MissingDistrict + '=SUM(' + Col4Pivot + ')'
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 1, '') + ', ' +
'[population]=SUM(pt.[population]) FROM (SELECT District, ElimDist, a.[population]' +
',n=ROW_NUMBER() OVER (PARTITION BY ElimDist ORDER BY District) FROM Sweden a ' +
'CROSS APPLY (SELECT CASE WHEN district IN (' + @BaseDistricts + ') ' +
'THEN 0 ELSE 1 END) b(ElimDist) WHERE ElimDist = 1) d PIVOT (MAX(district) FOR n IN (' +
STUFF((
SELECT ',' + Col4Pivot
FROM SpecialVars
FOR XML PATH(''), TYPE).value('.', 'VARCHAR(MAX)'), 1, 1, '') +
')) pt) b'
END
EXEC sp_executesql @SQL2Keep
PRINT 'Completed calculation of solution number: ' + CAST(@SolutionCounter AS VARCHAR) + ' ' +
CONVERT(VARCHAR(100),GETDATE(),121)
-- Increment the solution counter and re-initialize all working variables
SELECT @SolutionCounter = @SolutionCounter + 1
,@CountOfn = 'n=12'
,@CountOfnp = 'np=4'
,@CountOfnt = 'nt=1'
,@Pop = 'population=base.[population]'
,@dall = 'dall=base.dall'
,@BaseDistricts = 'd1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12'
,@DistrictColumns = 'base.d1,base.d2,base.d3,d4,d5,d6,d7,d8,d9,d10,d11,d12'
,@CurrentTryCounter = 1
,@CurrentDistrict = 13
,@Lastn = NULL
,@Lastnp = NULL
,@Lastnt = NULL
,@WorkingCAs = ''
END -- Of WHILE (solution iterations)
END
GO
I know... That's a pretty convoluted SP. It does seem to work to my intention though.
You can now run the 10 solutions we set up as follows:
DECLARE @StartTime DATETIME = GETDATE()
EXEC GenerateSwedenRedistrictingSolutions 10 -- Run solutions 1 through 10
SELECT StartTime=@StartTime, EndTime=GETDATE(), TotalMS=DATEDIFF(millisecond, @StartTime, GETDATE())
SELECT * FROM dbo.Solutions
ORDER BY 2*np+3*nt DESC, SolutionID
This last script will take about 12.5 minutes to run through, but yours may take a little longer because SQL server was already trained on the first 2 solutions (once trained they only take a couple of seconds to run). Looking at the results in the Solutions table, we see that:
SolutionID=1: Matches the solution we provided earlier.
SolutionID=2: Now has the optimal doublets (16) and 10 triplets.
The other (random) solutions weren't nearly as good. Here is what SolutionID 2 looks like (you can run just the SQL stored in the Solutions column SQL4Solution to get just that one solution):
[2,47,58];[3,52];[6,13];[9,26];[35,63];[48];
[8,66];[25,55];[36,40];[11,64];[27,62];[28,59];[43,57];[23,32];[31,46];[1,12];[42,65];[10,45];
[30,37,41];[22,49,50];[7,14,24];[5,56,61];[4,38,54];[17,21,33];[18,53,60];[20,29,39];[16,34,44];
[15];[19];[51]
My idea at this point, is to try moving various triplets earlier in the packing order, by looking at the districts that were ineligible in SolutionID=2 (and then successive solution attempts).
Of course, a smarter person than me (but I may give it a try anyway) may be able to analyze the triplets in more depth to come up with an alternative packing order based on some other factor(s).
Another approach, may be to set up enough numbered n columns for all possible triplet sort combinations. And then let the SP rip through them all. At least it seems to process each additional solution in a linear time increment.
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
Eureka! I have just hit upon a method that generates "hundreds" of triplet combinations that can be combined 11 at a time to cover all the districts included in the triplets! And it does it in a reasonable run time.
I say "hundreds" because I'm not sure they're all unique, they may be permutations of the same combinations. So I need to work that out. But it is just window dressing.
Edit: There are actually 8 unique triplet combinations. I also need to work out if this approach will work on doublets but I think it will.
I've said it before, stay tuned! I'll post more code when I've got it all sorted out.
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
I haven't had a chance to come up for air to review the latest, but only 8 unique triplets? I get 162...
I did try to use the CTE in place of SW7/SW8, but after processing for an hour on the SW8 equivalent, I killed it. I must be missing something.
~Les
Dr. Les Cardwell, DCS-DSS
Enterprise Data Architect
Central Lincoln PUD -
Les Cardwell (7/10/2012)
I haven't had a chance to come up for air to review the latest, but only 8 unique triplets? I get 162...I did try to use the CTE in place of SW7/SW8, but after processing for an hour on the SW8 equivalent, I killed it. I must be missing something.
~Les
Patience kind sir! As any good programmer would on a long running solution, I had a governor in place to stop upon finding the first set of optimal triples!
Indeed, when I removed that governor, I found 162 triplet combinations that achieve the optimal solution.
Likewise, there are 58 optimal doublet solutions!
Combining these, we have 9396 (162*58) optimal re-districting solutions, for which I have compiled the final query. Putting it together in steps now for your perusal.
Soon, kind sir, soon! You will find that I think the whole thing will run in under 20 minutes.
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
How does generating all possible optimal solutions in under 6 minutes grab ya?
Attached is a write up on the solution including everything you need to run it yourself. I am interested in how the timing compares on your machine vs. your old solution.
For any interested parties that have been following with mirth my trials, tribulations and machinations on the road to a solution (god help me!) any solution to this challenge, but have corporate rules against downloading ZIP attachments, PM me your email address and I'd be happy to send it along.
I can't tell you how much fun this has been! Best forum post I've ever tackled.
My mantra: No loops! No CURSORs! No RBAR! Hoo-uh![/I]My thought question: Have you ever been told that your query runs too fast?
My advice:
INDEXing a poor-performing query is like putting sugar on cat food. Yeah, it probably tastes better but are you sure you want to eat it?
The path of least resistance can be a slippery slope. Take care that fixing your fixes of fixes doesn't snowball and end up costing you more than fixing the root cause would have in the first place.Need to UNPIVOT? Why not CROSS APPLY VALUES instead?[/url]
Since random numbers are too important to be left to chance, let's generate some![/url]
Learn to understand recursive CTEs by example.[/url]
[url url=http://www.sqlservercentral.com/articles/St -
Ha! I'm glad I could send you on such an adventure 🙂
I'll run both for time comparisons this weekend when there's not much activity on this server (this has been one of those server nightmares where the vendor's specs we're not even close to what it took to bring things under control).
On the plus side, I learned a great deal about CTE's.
Left wanting is the elusive MK solution, but JC's bin packing methodology opened a door. More fodder for meditation in waiting rooms.
Dr. Les Cardwell, DCS-DSS
Enterprise Data Architect
Central Lincoln PUD
Viewing 15 posts - 91 through 105 (of 109 total)
You must be logged in to reply to this topic. Login to reply