Lists, Sets and a Little Math

In the previous post I've shown how a delimited list can be transformed in a table with the help of table-valued functions, and I gave as example a JOIN which provided the common elements between two lists:

-- intersection of two sets
SELECT A.* 
FROM dbo.SplitList('23 34 50 71', ' ') A 
     JOIN dbo.SplitList('23,34,25,45', ',') B 
    ON A.Value = B.Value 

A list is a collection of elements which can repeat in the list. When the elements of a list don't repeat we can talk about a set. Sets considered in combination with reunion, intersection, (set) difference, cartesian product and power set forms the basis of topology, however the most interesting part is when we start taking elements from the set or combining the elements of sets.

Arrangements with repetition, called also n-tuples of m-sets, given the fact that the arrangements are created by taking n elements from m sets. The number of elements is given by the formula: m^n. Thus, the arrangements of 2, 3, 4 elements with repetition will give 16, 64, respectively 256 combinations:

 -- arrangements of 2 elements with repetition
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
    , dbo.SplitList('1,2,3,4', ',') B 

 ORDER BY A.Value, B.Value 
 
 -- arrangements of 3 elements with repetition
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
    , dbo.SplitList('1,2,3,4', ',') B
    , dbo.SplitList('1,2,3,4', ',') C 

 ORDER BY A.Value, B.Value, C.Value

 -- arrangements of 4 elements with repetition
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
    , dbo.SplitList('1,2,3,4', ',') B 
    , dbo.SplitList('1,2,3,4', ',') C 
    , dbo.SplitList('1,2,3,4', ',') D 

ORDER BY A.Value, B.Value, C.Value, D.Value 

Combinations are selections of items, such that the order of selection does not matter, though the elements don't repeat inside of the n-tuple. Combinations of 4 elements taken as 2, 3, respectively 4:

 -- combinations of 4 elements taken as 2
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
      JOIN  dbo.SplitList('1,2,3,4', ',') B  
        ON A.Value < B.Value 

 ORDER BY A.Value, B.Value
 
 -- combinations of 4 elements taken as 3
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
       JOIN dbo.SplitList('1,2,3,4', ',') B
  ON A.Value < B.Value 
            JOIN  dbo.SplitList('1,2,3,4', ',') C 
       ON B.Value < C.Value 

 ORDER BY A.Value, B.Value, C.Value

 -- combinations of 4 elements taken as 4
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
      JOIN dbo.SplitList('1,2,3,4', ',') B 
 ON A.Value < B.Value 
           JOIN dbo.SplitList('1,2,3,4', ',') C 
      ON B.Value < C.Value 
                JOIN dbo.SplitList('1,2,3,4', ',') D 
    ON C.Value < D.Value 

 ORDER BY A.Value, B.Value, C.Value, D.Value 

Permutations, in exchange, involve arranging the elements of a set by interchanging their position. The permutations of 4 elements are given by following code:

 -- permutations of 4 elements 
 SELECT * 
 FROM dbo.SplitList('1,2,3,4', ',') A 
      JOIN dbo.SplitList('1,2,3,4', ',') B 
 ON A.Value <> B.Value 
           JOIN dbo.SplitList('1,2,3,4', ',') C 
             ON B.Value <> C.Value 
     AND A.Value <> C.Value 
         JOIN dbo.SplitList('1,2,3,4', ',') D 
    ON C.Value <> D.Value 
          AND B.Value <> D.Value 
   AND A.Value <> D.Value 
 ORDER BY A.Value, B.Value, C.Value, D.Value 

In praxis there are specific algorithms for generating the arrangements, combinations or permutations of a set, however I think that the above examples are simpler to understand as they reflect also the mathematical heuristic. The downside is that the complexity of the queries increases with the number of elements in the set.

In the end here's a fun example on how simple propositions can be created:

 -- creating propositions
 SELECT 'The ' + A.Value + ' ' + B.Value + ' ' + C.Value + '!' 
 FROM dbo.SplitList('cat,dog,bird,fish', ',') A 
    , dbo.SplitList('drinks,smells,eats,jumps', ',') B 
    , dbo.SplitList('loudly,nicely,grumpy,alone', ',') C 

Happy Coding!