Complex variable length string combination problem

Hi,
I'm having trouble finding a solution for the following problem:
Suppose you have the following string as input 'sig, ltw, onss'
I would like to generate the following result set:
sig
ltw
onss
sig, ltw
sig, onss
ltw, onns
sig, ltw, onss
This should also work for any number of names (each time seperated by a
comma) within the string ex.:
input = 'sig, ltw, onss, plk'
output =
sig
ltw
onss
plk
sig, ltw
sig, onss
sig, plk
ltw, onns
ltw, plk
onss, plk
sig, ltw, onss
sig, onss, plk
ltw, onss, plk
sig, ltw, onss, plk
Anyone an idea how to resolve this problem?
Thanx in advance...Why don't you put this data in a table rather than a delimited string? TSQL
really isn't a language for string manipulation and delimited data just
shouldn't exist in the database.
The permutations you want to output could be achieved with a self- CROSS
JOIN once you've put the data in a table.
David Portas
SQL Server MVP
--|||You can also do it with the ROLLUP operator:
CREATE TABLE foo (x VARCHAR(5) PRIMARY KEY)
INSERT INTO foo VALUES ('sig')
INSERT INTO foo VALUES ('ltw')
INSERT INTO foo VALUES ('onss')
SELECT A.x, B.x, C.x
FROM foo AS A
JOIN foo AS B
ON B.x <> A.x
JOIN foo AS C
ON C.x <> A.x
AND C.x <> B.x
GROUP BY A.x, B.x, C.x WITH ROLLUP
David Portas
SQL Server MVP
--|||Hi,
I agree that string manipulation is not so easy in T-SQL.
Suppose I put the words as rows in a table; the problem with the crossjoin
is that it returns too many possiblities that are not usefull to me:
given a, b, c
the crossjoin would generate:
a, a, a
a, b, a
a, c, a
b, a, a => already exists but in another order
etc...
As you see whereas in my case I generate 14 possibilities for a 4 names
comma seperated string in your case this will be 27 possibilities; in other
words almost twice as many.
A solution would be to elimate from the crossjoin result the same occurences
of the names but in another order. But how?
"David Portas" wrote:

> Why don't you put this data in a table rather than a delimited string? TSQ
L
> really isn't a language for string manipulation and delimited data just
> shouldn't exist in the database.
> The permutations you want to output could be achieved with a self- CROSS
> JOIN once you've put the data in a table.
> --
> David Portas
> SQL Server MVP
> --|||This is pretty close; if we could just eliminate the "doubles" (in this case
the same names but in a different order) than I would be a happy man... ;-)
"David Portas" wrote:

> You can also do it with the ROLLUP operator:
> CREATE TABLE foo (x VARCHAR(5) PRIMARY KEY)
> INSERT INTO foo VALUES ('sig')
> INSERT INTO foo VALUES ('ltw')
> INSERT INTO foo VALUES ('onss')
> SELECT A.x, B.x, C.x
> FROM foo AS A
> JOIN foo AS B
> ON B.x <> A.x
> JOIN foo AS C
> ON C.x <> A.x
> AND C.x <> B.x
> GROUP BY A.x, B.x, C.x WITH ROLLUP
> --
> David Portas
> SQL Server MVP
> --
>|||Try this one then:
CREATE TABLE foo (x VARCHAR(5) PRIMARY KEY)
INSERT INTO foo VALUES ('sig')
INSERT INTO foo VALUES ('ltw')
INSERT INTO foo VALUES ('onss')
INSERT INTO foo VALUES ('')
SELECT A.x, NULLIF(B.x,''), NULLIF(C.x,'')
FROM foo AS A
LEFT JOIN foo AS B
ON B.x < A.x
LEFT JOIN foo AS C
ON C.x < B.x
WHERE A.x > ''
David Portas
SQL Server MVP
--|||David,
Great!!!! this is exactly what I need.
Is there an easy way to make this code dynamic as to receive any number of
input rows?
This already is great to work on...
thanx man! :-)
"David Portas" wrote:

> Try this one then:
> CREATE TABLE foo (x VARCHAR(5) PRIMARY KEY)
> INSERT INTO foo VALUES ('sig')
> INSERT INTO foo VALUES ('ltw')
> INSERT INTO foo VALUES ('onss')
> INSERT INTO foo VALUES ('')
> SELECT A.x, NULLIF(B.x,''), NULLIF(C.x,'')
> FROM foo AS A
> LEFT JOIN foo AS B
> ON B.x < A.x
> LEFT JOIN foo AS C
> ON C.x < B.x
> WHERE A.x > ''
> --
> David Portas
> SQL Server MVP
> --
>|||The following is really slow, (cause it's resursive), but it works...
First step would be to get the Indiv Strings into a table.. You can use the
following function for that... It's a generally useful function to have
around anyway...
Create Function dbo.ParseString (
@.S VarChar(8000),
@.delim Char(1))
Returns @.tOut Table (ValNum Integer Primary Key Identity, sVal VarChar(500)
)
As
Begin
Declare @.sVal VarChar(80)
Declare @.deLimPos Integer
If right(@.S,1) <> @.Delim Set @.S = @.S + @.Delim
While Len(@.S) > 0
Begin
Set @.deLimPos = CharIndex(@.delim, @.S)
Set @.sVal = Left(@.S,@.deLimPos -1)
Set @.S = Right(@.S,Len(@.S) - @.deLimPos)
Insert @.tOut (sVal) Values (@.sVal)
End
Return
End
-- ----
This function parses a string, using the supplied delimiter, and returns a
table with one row for each entry in the string.
Next, you need a function to "alphabeticize" a delimited string... This one
does the trick...
Create FUNCTION dbo.SortString
(@.S VarChar(1000), @.Delim Char(1))
RETURNS VarChar(1000)
AS
BEGIN
Declare @.Out VarChar(1000) Set @.Out = ''
Declare @.Vals Table (Val VarChar(100))
Declare @.Val VarChar(100)
Insert @.Vals(Val)
Select LTrim(sVal)
From dbo.ParseString(@.S, @.Delim)
While Exists(Select * From @.Vals) Begin
Select @.Val = Min(Val) From @.Vals
Set @.Out = @.Out + @.Val + ','
Delete @.Vals Where Val = @.Val
End
Return Substring(@.Out, 1, Len(@.Out) -1)
END
-- ----
Using these 2 functions, you can dynamically do what you want wit hteh
following:
assuming the variable @.Input contains the original concatenated string...
Declare @.Input VarChar(100) Set @.Input = 'a, b, c'
Declare @.Items Table (ItmNo Integer Primary Key Identity, item varchar(50))
Declare @.Permutations Table(Permutation VarChar(1000))
Insert @.Items (Item)
Select sVal
From dbo.ParseString(@.Input , ',')
Order By sVal
-- ---
--Select * From @.Items
Declare @.NumItems TinyInt
Declare @.Size TinyInt Set @.Size = 0
Select @.NumItems = Count(*) From @.Items
While @.Size <= @.NumItems Begin
Insert @.Permutations (Permutation)
Select Distinct dbo.SortString(IsNull(P.Permutation + ', ', '') +
I.Item, ',')
From @.Items I Left Join @.Permutations P
On I.Item <> IsNull(P.Permutation,'')
Where Not Exists(Select * From @.Permutations
Where Permutation =
dbo.SortString(IsNull(P.Permutation + ', ', '') +
I.Item, ','))
And CharIndex(I.Item, IsNull(P.Permutation,'')) = 0
Set @.Size = @.Size + 1
End
Insert @.Permutations(Permutation) Values('')
Select * From @.Permutations|||Thanks man for your effort.
Will stick to the answer of David Portas found it very elegant.
"CBretana" wrote:

> The following is really slow, (cause it's resursive), but it works...
> First step would be to get the Indiv Strings into a table.. You can use th
e
> following function for that... It's a generally useful function to have
> around anyway...
> Create Function dbo.ParseString (
> @.S VarChar(8000),
> @.delim Char(1))
> Returns @.tOut Table (ValNum Integer Primary Key Identity, sVal VarChar(50
0))
> As
> Begin
> Declare @.sVal VarChar(80)
> Declare @.deLimPos Integer
> If right(@.S,1) <> @.Delim Set @.S = @.S + @.Delim
> While Len(@.S) > 0
> Begin
> Set @.deLimPos = CharIndex(@.delim, @.S)
> Set @.sVal = Left(@.S,@.deLimPos -1)
> Set @.S = Right(@.S,Len(@.S) - @.deLimPos)
> Insert @.tOut (sVal) Values (@.sVal)
> End
> Return
> End
> -- ----
> This function parses a string, using the supplied delimiter, and returns a
> table with one row for each entry in the string.
> Next, you need a function to "alphabeticize" a delimited string... This on
e
> does the trick...
> Create FUNCTION dbo.SortString
> (@.S VarChar(1000), @.Delim Char(1))
> RETURNS VarChar(1000)
> AS
> BEGIN
> Declare @.Out VarChar(1000) Set @.Out = ''
> Declare @.Vals Table (Val VarChar(100))
> Declare @.Val VarChar(100)
> Insert @.Vals(Val)
> Select LTrim(sVal)
> From dbo.ParseString(@.S, @.Delim)
> While Exists(Select * From @.Vals) Begin
> Select @.Val = Min(Val) From @.Vals
> Set @.Out = @.Out + @.Val + ','
> Delete @.Vals Where Val = @.Val
> End
> Return Substring(@.Out, 1, Len(@.Out) -1)
> END
> -- ----
> Using these 2 functions, you can dynamically do what you want wit hteh
> following:
> assuming the variable @.Input contains the original concatenated string...
> Declare @.Input VarChar(100) Set @.Input = 'a, b, c'
> Declare @.Items Table (ItmNo Integer Primary Key Identity, item varchar(50)
)
> Declare @.Permutations Table(Permutation VarChar(1000))
> Insert @.Items (Item)
> Select sVal
> From dbo.ParseString(@.Input , ',')
> Order By sVal
> -- ---
> --Select * From @.Items
> Declare @.NumItems TinyInt
> Declare @.Size TinyInt Set @.Size = 0
> Select @.NumItems = Count(*) From @.Items
>
> While @.Size <= @.NumItems Begin
> Insert @.Permutations (Permutation)
> Select Distinct dbo.SortString(IsNull(P.Permutation + ', ', '') +
> I.Item, ',')
> From @.Items I Left Join @.Permutations P
> On I.Item <> IsNull(P.Permutation,'')
> Where Not Exists(Select * From @.Permutations
> Where Permutation =
> dbo.SortString(IsNull(P.Permutation + ', ', '')
+
> I.Item, ','))
> And CharIndex(I.Item, IsNull(P.Permutation,'')) = 0
> Set @.Size = @.Size + 1
> End
> Insert @.Permutations(Permutation) Values('')
> Select * From @.Permutations
>|||No problemo Peter,
David's solution is much more elegant, and much faster, but as you noticed,
it not dynamic as to the number of items in the imput string...
But as I'm sure you have already figured out, the required processing to
solve this problem increases very very fast as the number of items increases
.
Regards,
Charly
"PeterM" wrote:
> Thanks man for your effort.
> Will stick to the answer of David Portas found it very elegant.
> "CBretana" wrote:
>

Complex variable length combinations of a string

Hi,
Could anyone help me with the following complex problem:
Suppose I have the following input: 'sig, ltw, onss'
Than my output should give the following result set:
sig
ltw
onss
sig, ltw
sig, onss
ltw, onss
sig, ltw, onss
The solution should also work with any given number of names in my comma
seperated string ex.:
input = sig, ltw, onss, pkl
output =
sig
ltw
onss
pkl
sig, ltw
sig, onss
sig, pkl
ltw, onss
ltw, pkl
onss, pkl
sig, ltw, onss
sig, onss, pkl
ltw, onss, pkl
sig, ltw, onss, pkl
Anyone an idea how to resolve this with T-SQL?
Thanx...Peter,
Took me some time to figure this out:
set nocount on
declare @.str as varchar(8000)
,@.count as int
,@.out as varchar(8000)
create table #str
(i int identity(0, 1)
, el varchar(4000))
set @.str='sig, ltw, onss'
--extract elements into a table
set @.str = @.str + ','
while @.str <> '' begin
insert into #str (el)
values (substring(@.str, 1, charindex(',', @.str) - 1))
set @.str = ltrim(substring(@.str, charindex(',', @.str) + 1, 8000))
end
--calculate number of combinations
select @.count = power(2, count(*)) - 1 from #str
--create all combinations
--each element as a binary position where
--1 means element is in and 0 means element is not in a given combination
while @.count > 0 begin
set @.out = ''
select @.out = @.out + el + ', '
from #str
where @.count & power(2, i) = power(2, i)
order by i
select left(@.out, len(@.out) - 1)
set @.count = @.count - 1
end
drop table #str
Ilya
"PeterM" <PeterM@.discussions.microsoft.com> wrote in message
news:A2E5AF3D-4AEF-4E79-9395-639513E06D4E@.microsoft.com...
> Hi,
> Could anyone help me with the following complex problem:
> Suppose I have the following input: 'sig, ltw, onss'
> Than my output should give the following result set:
> sig
> ltw
> onss
> sig, ltw
> sig, onss
> ltw, onss
> sig, ltw, onss
> The solution should also work with any given number of names in my comma
> seperated string ex.:
> input = sig, ltw, onss, pkl
> output =
> sig
> ltw
> onss
> pkl
> sig, ltw
> sig, onss
> sig, pkl
> ltw, onss
> ltw, pkl
> onss, pkl
> sig, ltw, onss
> sig, onss, pkl
> ltw, onss, pkl
> sig, ltw, onss, pkl
> Anyone an idea how to resolve this with T-SQL?
> Thanx...
>|||Ilya, Thanks for your effort in resolving this; but look at the post just
before (Oops I sended it twice) the answer of David Portas is such a elegant
solution, you have to see it to belief it :-)
Thanx
"Ilya Margolin" wrote:

> Peter,
> Took me some time to figure this out:
> set nocount on
> declare @.str as varchar(8000)
> ,@.count as int
> ,@.out as varchar(8000)
> create table #str
> (i int identity(0, 1)
> , el varchar(4000))
> set @.str='sig, ltw, onss'
> --extract elements into a table
> set @.str = @.str + ','
> while @.str <> '' begin
> insert into #str (el)
> values (substring(@.str, 1, charindex(',', @.str) - 1))
> set @.str = ltrim(substring(@.str, charindex(',', @.str) + 1, 8000))
> end
> --calculate number of combinations
> select @.count = power(2, count(*)) - 1 from #str
> --create all combinations
> --each element as a binary position where
> --1 means element is in and 0 means element is not in a given combination
> while @.count > 0 begin
> set @.out = ''
> select @.out = @.out + el + ', '
> from #str
> where @.count & power(2, i) = power(2, i)
> order by i
> select left(@.out, len(@.out) - 1)
> set @.count = @.count - 1
> end
> drop table #str
> Ilya
>
> "PeterM" <PeterM@.discussions.microsoft.com> wrote in message
> news:A2E5AF3D-4AEF-4E79-9395-639513E06D4E@.microsoft.com...
>
>|||Peter,
That was my first thought. The downside of it you have to modify the
statement to add more joins as you add combination members, so the solution
is not scalable.
Ilya
"PeterM" <PeterM@.discussions.microsoft.com> wrote in message
news:D5230490-26F4-4E72-915B-53688DFFC618@.microsoft.com...
> Ilya, Thanks for your effort in resolving this; but look at the post just
> before (Oops I sended it twice) the answer of David Portas is such a
elegant
> solution, you have to see it to belief it :-)
> Thanx
> "Ilya Margolin" wrote:
>
combination
comma|||You're right !
I was wondering how big the difference in performance is between the two
solutions? Have to try it out...
Thanx again :-)
"Ilya Margolin" wrote:

> Peter,
> That was my first thought. The downside of it you have to modify the
> statement to add more joins as you add combination members, so the solutio
n
> is not scalable.
> Ilya
> "PeterM" <PeterM@.discussions.microsoft.com> wrote in message
> news:D5230490-26F4-4E72-915B-53688DFFC618@.microsoft.com...
> elegant
> combination
> comma
>
>|||Ilya,
I had to write you back to say that your solution is by far the most elegant
of all.
I had to take some time to understand your solution but once I understood
it; I found it just brilliant.
Sorry for this late appreciation of your solution ;-)
Thanx again,
Peter
"Ilya Margolin" wrote:

> Peter,
> That was my first thought. The downside of it you have to modify the
> statement to add more joins as you add combination members, so the solutio
n
> is not scalable.
> Ilya
> "PeterM" <PeterM@.discussions.microsoft.com> wrote in message
> news:D5230490-26F4-4E72-915B-53688DFFC618@.microsoft.com...
> elegant
> combination
> comma
>
>