The other day, a guy came to me with a requriement saying he wanted to generate all possible combinations of a given set of natural numbers, in query. For a set 1,2,3, he wanted the result as 1,2,3,2-3, 3-1, 1-3, 1-2-3. With some contemplation, I understood that he wanted nC1+nC2+nC3+…..nCn. I started jotting down the queries and I was surprised to see some interesting patterns:
A self join would generate duo-combinations of patterns with duplicates
declare @Animal table
(
AnimalName varchar(100)
)
insert into @Animal values (’Lion’)
insert into @Animal values (’Tiger’)
insert into @Animal values (’Horse’)
insert into @Animal values (’Elephant’)
select A.AnimalName , B.AnimalName from @Animal A, @Animal B
To minimize the Duplicates:
select A.AnimalName , B.AnimalName from @Animal A, @Animal B
where A.AnimalName <> B.AnimalName
But then, there are same set of elements ordered in a different way, like (Lion, Tiger) and (Tiger, Lion). To minimize this, try the following
select A.AnimalName , B.AnimalName from @Animal A, @Animal B
where A.AnimalName <> B.AnimalName and A.AnimalName < B.AnimalName
The count of result set is obviously nC2. If I should extent this to three elements then I can try adding one more join:
select A.AnimalName , B.AnimalName, C.AnimalName from @Animal A, @Animal B, @Animal C
where (A.AnimalName <> B.AnimalName and B.AnimalName <> C.AnimalName and
A.AnimalName <> C.AnimalName )and
A.AnimalName < B.AnimalName and B.AnimalName < C.AnimalName
The count of result set is nC3. But would not it be difficult to keep on adding self joins, as the set count increases.
Lets try a different way. Lets generalise the elements of the set as (1), (2), (3),… instead of the actual contents. Will CharIndex help in any way. This is what I tried.
select A.AnimalName + ‘ and ‘ + B.AnimalName AnimalName
from (select A.AnimalName + ‘ and ‘ + B.AnimalName AnimalName from @Animal A, @Animal B
where A.AnimalName <> B.AnimalName ) A, @Animal B
where A.AnimalName <> B.AnimalName and charindex (B.AnimalName, A.AnimalName) = 0
and A.AnimalName < B.AnimalName
select A.AnimalName + ‘ and ‘ + B.AnimalName AnimalName from
(
select A.AnimalName + ‘ and ‘ + B.AnimalName AnimalName
from
(select A.AnimalName + ‘ and ‘ + B.AnimalName AnimalName from @Animal A, @Animal B
where A.AnimalName <> B.AnimalName ) A, @Animal B
where A.AnimalName <> B.AnimalName and charindex (B.AnimalName, A.AnimalName) = 0
) A, @Animal B
where A.AnimalName <> B.AnimalName and charindex (B.AnimalName, A.AnimalName) = 0
It was not fruitful though. It seems to generate Permutational patterns rather than combinational ones. Hence, what would be the ideal way to generate combinational patterns without increasing the number of self joins based on the set count. One way I could think is to create a function which will accept the incoming result set and join it with the table. The function itself would be joined with the table, recursively to get the desired result set. This is ofcourse, an other way of self join without making the query bigger. To pass the result set to the function, will the function allow Table variables as arguments. Yes it is in case of SQL 2008. In case of SQL2000, we have to resort to the traditional approach in sending XML data and use Open Query inside the function. I feel, We can eaily generate the patterns using Common Table Expressions in SQL 2005.
Note: The entire content is written on the fly. Hence try this out in SQL and then take a judgement. I welcome you for any corrections in the post.
breathesoftware.wordpress.com 