Combinations and Permutations

• Steve Jones - SSC Editor

  SSC Guru

  Points: 738127

  More actions

  May 18, 2011 at 10:34 am

  #239764

  Does anyone have a nice T-SQL solution for combinations? I got the idea from http://www.sqlservercentral.com/Forums/Topic1110305-1292-1.aspx

  The OP doesn't need one, but I ran into this complicated way for 3 values.

  CREATE TABLE Combinations

  ( id int)

  GO

  INSERT Combinations select 1

  INSERT Combinations select 2

  INSERT Combinations select 3

  SELECT a.id 'a', b.id 'b', c.id 'c'

  FROM Combinations a

  CROSS JOIN dbo.Combinations b

  CROSS JOIN dbo.Combinations c

  WHERE a.id != b.id

  AND a.id != c.id

  AND b.id != c.id

  ORDER BY

  a, b, c

  DROP TABLE Combinations

  If I add two more rows, then 5 looks like this:

  SELECT a.id 'a', b.id 'b', c.id 'c', d.id 'd', e.id 'e'

  FROM Combinations a

  CROSS JOIN dbo.Combinations b

  CROSS JOIN dbo.Combinations c

  CROSS JOIN dbo.Combinations d

  CROSS JOIN dbo.Combinations e

  WHERE a.id != b.id

  AND a.id != c.id

  AND a.id != d.id

  AND a.id != e.id

  AND b.id != c.id

  AND b.id != d.id

  AND b.id != e.id

  AND c.id != d.id

  AND c.id != e.id

  AND d.id != e.id

  ORDER BY a, b, c, d

  Ugly and seems wrong.

• Brandie Tarvin

  SSC Guru

  Points: 173105

  More actions

  May 18, 2011 at 11:09 am

  #1326660

  Steve,

  I actually have a table in an analytics database where I had to set something like this up, but the numbers are so small that I just entered them into the table manually. The numbers are switches that connect to other tables and tell the monthly data update which set of values to use for the calculations.

  But out of curiosity, what would be your reason for using these combinations? So I could work on a prettier solution.

  Brandie Tarvin, MCITP Database AdministratorLiveJournal Blog: http://brandietarvin.livejournal.com/[/url]On LinkedIn!, Google+, and Twitter.Freelance Writer: ShadowrunLatchkeys: Nevermore, Latchkeys: The Bootleg War, and Latchkeys: Roscoes in the Night are now available on Nook and Kindle.

• LutzM

  SSC Guru

  Points: 107049

  More actions

  May 18, 2011 at 11:11 am

  #1326664

  Something like this?

  SELECT a.id 'a', b.id 'b', c.id 'c', d.id 'd', e.id 'e'

  FROM Combinations a

  CROSS JOIN dbo.Combinations b

  CROSS JOIN dbo.Combinations c

  CROSS JOIN dbo.Combinations d

  CROSS JOIN dbo.Combinations e

  WHERE a.id+b.id+c.id+d.id+e.id = 15

  AND a.id*b.id*c.id*d.id*e.id = 120

  ---

  
  Lutz
  A pessimist is an optimist with experience.

  How to get fast answers to your question[/url]
  How to post performance related questions[/url]
  Links for Tally Table [/url] , Cross Tabs [/url] and Dynamic Cross Tabs [/url], Delimited Split Function[/url]

• Brandie Tarvin

  SSC Guru

  Points: 173105

  More actions

  May 18, 2011 at 11:21 am

  #1326673

  Boys, you should be ashamed of yourselves. Jeff Moden gave us a better way.

  DECLARE @MaxTally int;

  SELECT @MaxTally = Max(ID) FROM dbo.Combinations;

  SELECT c.ID, t.N AS TallyID

  FROM dbo.Combinations c

  CROSS JOIN dbo.Tally t

  WHERE t.N <= @MaxTally;

  Brandie Tarvin, MCITP Database AdministratorLiveJournal Blog: http://brandietarvin.livejournal.com/[/url]On LinkedIn!, Google+, and Twitter.Freelance Writer: ShadowrunLatchkeys: Nevermore, Latchkeys: The Bootleg War, and Latchkeys: Roscoes in the Night are now available on Nook and Kindle.

• Evil Kraig F

  SSC Guru

  Points: 100851

  More actions

  May 18, 2011 at 11:55 am

  #1326689

  All I've got is an equivalent method that uses joins/ons instead of leaving it all in the WHERE clause, but it's the same execution plan. Subquery had the same issue. Hrm.

  I tried a few different ways, including some force orders, but none of them actually changed the execution plan to the better nor really changed the methodology.

  ---

  - Craig Farrell

  Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

  For better assistance in answering your questions[/url] | Forum Netiquette
  For index/tuning help, follow these directions.[/url] |Tally Tables[/url]
  Twitter: @AnyWayDBA

• Evil Kraig F

  SSC Guru

  Points: 100851

  More actions

  May 18, 2011 at 12:01 pm

  #1326692

  Brandie Tarvin (5/18/2011)

  ---

  Boys, you should be ashamed of yourselves. Jeff Moden gave us a better way.

  DECLARE @MaxTally int;

  SELECT @MaxTally = Max(ID) FROM dbo.Combinations;

  SELECT c.ID, t.N AS TallyID

  FROM dbo.Combinations c

  CROSS JOIN dbo.Tally t

  WHERE t.N <= @MaxTally;

  Completely different set of results there, Brandie. One, they're unpivoted. Two, you're allowing for matching. Three, that doesn't deal with the full combination spectrum of 1/2/3/4/5 and 5/4/3/2/1. I thought about a triangle join mechanism which would do the equivalent of only half the results and discarded it, unfortunately.

  You should be getting 120 rows back for a 5 way combination.

  ---

  - Craig Farrell

  Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

  For better assistance in answering your questions[/url] | Forum Netiquette
  For index/tuning help, follow these directions.[/url] |Tally Tables[/url]
  Twitter: @AnyWayDBA

• GSquared

  SSC Guru

  Points: 260824

  More actions

  May 18, 2011 at 12:21 pm

  #1326701

  It depends on what you're trying to get as an end result.

  Are you trying to get a grid with:

  a,b,c

  b,c,a

  c,b,a

  b,a,c

  a,c,b

  c,a,b

  c,b,a

  And variations with more columns, with no repeating values in a single row? (No a,a,a or a,b,b combinations, for example.)

  If so, then the cross-join version or a cross apply version, is the easiest way to do it.

  You can generate the combinations vertically and then pivot them, but that's even more work and even less readable code. For that matter, you could use a recursive CTE to generate all combinations, then use PIVOT to turn it horizontal on a CombinationID column, and make it even more obscure and even slower.

  Should look something like this:

  USE ProofOfConcept;

  GO

  IF OBJECT_ID(N'tempdb..#Values') IS NOT NULL

  DROP TABLE #Values;

  CREATE TABLE #Values (

  Val CHAR(1) PRIMARY KEY);

  INSERT INTO #Values (Val)

  VALUES ('a'),('b'),('c');

  SELECT *

  FROM #Values AS V1

  INNER JOIN #Values AS V2

  ON V1.Val != V2.Val

  INNER JOIN #Values AS V3

  ON V2.Val != V3.Val

  AND V1.Val != V3.Val;

  Note that, as you add columns, your join criteria have to include all prior instances of the table in the From clause. If you had a V4, it would have to have a value not in V1, V2, or V3, or you can end up with repeating values. This gets cumbersome when you get large numbers of values to grid this way.

  A sort of extreme version of it could theoretically be used to solve Soduku problems. You treat the grid as a single, 81-column row, and you just have to work the Joins to make sure both the various no-repeats are true and the math is right. Then it's just a matter of the right parameters for the inputs. Don't try this, it's more CPU time than you want to deal with. It's just a theoretical exercise.

  - Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
  Property of The Thread

  "Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon

• mister.magoo

  SSC-Forever

  Points: 47174

  More actions

  May 18, 2011 at 12:23 pm

  #1326702

  You can certainly simplify the code, but probably not the plan....

  SELECT a.id 'a', b.id 'b', c.id 'c', d.id 'd', e.id 'e'

  FROM Combinations a

  CROSS JOIN dbo.Combinations b

  CROSS JOIN dbo.Combinations c

  CROSS JOIN dbo.Combinations d

  CROSS JOIN dbo.Combinations e

  WHERE a.id not in (b.id,c.id,d.id,e.id)

  AND b.id not in (a.id,c.id,d.id,e.id)

  AND c.id not in (a.id,b.id,d.id,e.id)

  AND d.id not in (a.id,b.id,c.id,e.id)

  AND e.id not in (a.id,b.id,c.id,d.id)

  MM
  

  ---

  
  select geometry::STGeomFromWKB(0x0106000000020000000103000000010000000B0000001000000000000840000000000000003DD8CCCCCCCCCC0840000000000000003DD8CCCCCCCCCC08408014AE47E17AFC3F040000000000104000CDCCCCCCCCEC3F9C999999999913408014AE47E17AFC3F9C99999999991340000000000000003D0000000000001440000000000000003D000000000000144000000000000000400400000000001040000000000000F03F100000000000084000000000000000401000000000000840000000000000003D0103000000010000000B000000000000000000143D000000000000003D009E99999999B93F000000000000003D009E99999999B93F8014AE47E17AFC3F400000000000F03F00CDCCCCCCCCEC3FA06666666666FE3F8014AE47E17AFC3FA06666666666FE3F000000000000003D1800000000000040000000000000003D18000000000000400000000000000040400000000000F03F000000000000F03F000000000000143D0000000000000040000000000000143D000000000000003D, 0);

• Forum Etiquette: How to post Reporting Services problems
[/url]
• Forum Etiquette: How to post data/code on a forum to get the best help - by Jeff Moden
[/url]
• How to Post Performance Problems - by Gail Shaw
[/url]