How to Generate Permutations in SQL

I  have 8 categories - A, B, C, D, E, F, G & H.

I want to create groups that reflect every single combination of these categories without there being duplicates.  Is this even possible.  I am obliged to think, but i am not sure how.  Any assistance from the experts will be greatly appreciated.  The groups would look like followings:

A
B
C
D
E
A, B
A, C
A, D
A, E
B, C
B, D
B, E
C, D . . . etc.

Thanks,
LVL 1
fb1990Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

slightwv (䄆 Netminder) Commented:
For a 'combination' I don't see how the individual ones are possible.

If you want AB to GH, try this (Oracle tested):
with mydata as (
	select 'A' mycol from dual
	union all
	select 'B' mycol from dual
	union all
	select 'C' mycol from dual
	union all
	select 'D' mycol from dual
	union all
	select 'E' mycol from dual
	union all
	select 'F' mycol from dual
	union all
	select 'G' mycol from dual
	union all
	select 'H' mycol from dual
)
select c1.mycol, c2.mycol 
from mydata c1 
	cross join mydata c2 
where c1.mycol < c2.mycol
order by c1.mycol, c2.mycol
/

Open in new window

0
Koen Van WielinkBusiness Intelligence SpecialistCommented:
The best solution is probably a recursive CTE which unions on itself to get all possilbe combinations. I have to admit I did have to look around on the internet for similar solutions to get the details right, but here's a working CTE:

declare @categories table
(
	ID		nvarchar(max)
,	CatCode nvarchar(max)
)

insert into @categories
values ('01', 'A'), ('02', 'B'), ('03', 'C'), ('04', 'D'), ('05', 'E'), ('06', 'F'), ('07', 'G'), ('08', 'H');

Declare	@counter int
Select	@counter = COUNT(*)
from	@categories;

With Permutations (permutation, IDs, Depth)
as
(
Select		c.CatCode
		,	c.ID + ';'
		,	Depth = 1
From	@categories c

union all

Select		permutation + c.CatCode
		,	IDs + ID + ';'
		,	Depth = Depth + 1
from		@categories as c
		,	Permutations as p
Where	p.Depth < @counter
AND		IDs not like '%' + ID + ';%'
)

Select *
from	Permutations
where	Depth = @counter
order by permutation

Open in new window


What it does is start with a table variable containing A to H and a corresponding number.  This is read into a common table expression, appending a semicolon to the ID column and setting Depth to 1. This indicates those are all the possible combinations of length 1.
It then unions on itself, adding the next letter to the permutation column, where the depth is smaller than the total number of letters (@counter) and the IDs column is not equal to something like the ID currently processed. Since these are permutations you don't want any repetitions.
Since you mention permutations, which for A to H means all the 8 character possibliities only, you can then select from the permutations CTE where depth = @counter. However, based on your example output, you're actually looking for all permutations of ANY length. In that case you would want to remove the "Where depth = @counter" clause.
Hope this works for you.
0
Koen Van WielinkBusiness Intelligence SpecialistCommented:
Sorry, just realized you asked Oracle syntax. I'm sorry to say I'm not familiar with Oracle, but I'm sure the same logic can be applied to an Oracle database. It seems that Oracle supports a very similary syntax since version 11g release 2, but calls it recursive subquery factoring.
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

Tomas Helgi JohannssonCommented:
Hi!

This is a simple task. If you have a table T with a column cat as the category column then you can simply do it like this.

select t1.cat, '' cat
from T t1
union
select t2.cat, t3.cat
from T t2, T t3
where t2.cat <> t3.cat

Open in new window

This would give you 64 rows.

Regards,
    Tomas Helgi
0
awking00Commented:
Are the categories truly A though H or can they be something different? Also, do you need pure sql or can it be PL/SQL?
0
awking00Commented:
This can easily be accomplished using pl/sql to insert into a table.
SQL> select * from categories;

C
-
A
B
C
D
E
F
G
H
create table permutations(category1 varchar2(1), category2 varchar2(1));
begin
for i in ascii('A')..ascii('H') loop
 for j in 1+i..ascii('H') loop
  insert into permutations values(chr(i), chr(j));
 end loop;
end loop;
end;
/
begin
for i in ascii('A')..ascii('H') loop
 for j in 1+i..ascii('H') loop
  insert into permutations values(chr(i), chr(j));
 end loop;
end loop;
end;
/
begin
for i in ascii('A')..ascii('H') loop
 for j in 1+i..ascii('H') loop
  insert into permutations values(chr(i), chr(j));
 end loop;
end loop;
end;
/
SQL> select * from permutations;
C C
- -
A B
A C
A D
A E
A F
A G
A H
B C
B D
B E
B F
B G
B H
C D
C E
C F
C G
C H
D E
D F
D G
D H
E F
E G
E H
F G
F H
G H
0
awking00Commented:
Don't know why procedure got repeated.
SQL> select * from categories;
C
-
A
B
C
D
E
F
G
H
create table permutations(category1 varchar2(1), category2 varchar2(1));
begin
for i in ascii('A')..ascii('H') loop
 for j in 1+i..ascii('H') loop
  insert into permutations values(chr(i), chr(j));
 end loop;
end loop;
end;
/
SQL> select * from permutations;
C C
- -
A B
A C
A D
A E
A F
A G
A H
B C
B D
B E
B F
B G
B H
C D
C E
C F
C G
C H
D E
D F
D G
D H
E F
E G
E H
F G
F H
G H
0
slightwv (䄆 Netminder) Commented:
awking00,

Seems that produces the same output as my post above but uses pl/sql.  PL/SQL is unnecessary.
0
Koen Van WielinkBusiness Intelligence SpecialistCommented:
The poster is asking for all possible combinations of 8 letters, not just combinations of 2. Only a recursion can achieve this as far as I know.
0
awking00Commented:
I guess I misunderstood the request. So the "etc." from the example would also include?
A,B,C
A,B,D
A,B,E
B,C,D
B,C,E
C,D,E
A,B,C,D
A,B,C,E
etc.
0
Koen Van WielinkBusiness Intelligence SpecialistCommented:
That's how I understood it. Seems the asker has disappeared though...
0
fb1990Author Commented:
Yes, I am looking for permutation of 8 letters as shown in my example with all the possible combinations without repetition these site has an example of permutation of 5 letters..
http://math.stackexchange.com/questions/161565/what-is-the-total-number-of-combinations-of-5-items-together-when-there-are-no-d

I am still here Koen...smile

Thanks.
0
slightwv (䄆 Netminder) Commented:
I'm a database guy.  I'm not a math guy so can you add to your original requirements?

So you want A through ABCDEFGH?

I get the first value is 'A'.  What is the last value you want?

What database (you posted in two topic areas)?
Does it have to be straight SQL or can we use procedural code?
What is the result set?  A cursor, output to the screen, an array?

Please clarify the requirements...

If you have been around all the time, it would have helped solve the problem faster had you added to the conversation.

Less guessing on our parts...
0
Koen Van WielinkBusiness Intelligence SpecialistCommented:
Have you tried my query on oracle? The logic generates exactly what you want. Just not sure if the syntax is 100% the same, but from what I've read it is very similar.
0
sdstuberCommented:
In Oracle 11gR2 and above the syntax is even easier,  the functionality is built in.

You do need to create a collection type though first

CREATE OR REPLACE TYPE vcarray AS TABLE OF VARCHAR2(4000);

WITH yourdata
     AS (    SELECT SUBSTR('ABCDEFGH', LEVEL, 1) cat
               FROM DUAL
         CONNECT BY LEVEL <= LENGTH('ABCDEFGH'))
  SELECT (SELECT LISTAGG(COLUMN_VALUE, ',') WITHIN GROUP (ORDER BY COLUMN_VALUE)
            FROM TABLE(x.COLUMN_VALUE))
             sets
    FROM TABLE(POWERMULTISET((SELECT CAST(COLLECT(cat) AS vcarray) FROM yourdata))) x
ORDER BY LENGTH(sets), sets;

Open in new window


or, if you are licensed for data mining you can use the built in type

WITH yourdata
     AS (    SELECT SUBSTR('ABCDEFGH', LEVEL, 1) cat
               FROM DUAL
         CONNECT BY LEVEL <= LENGTH('ABCDEFGH'))
  SELECT (SELECT LISTAGG(COLUMN_VALUE, ',') WITHIN GROUP (ORDER BY COLUMN_VALUE)
            FROM TABLE(x.COLUMN_VALUE))
             sets
    FROM TABLE(POWERMULTISET((SELECT CAST(COLLECT(cat) AS ora_mining_varchar2_nt) FROM yourdata))) x
ORDER BY LENGTH(sets), sets

Open in new window

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
sdstuberCommented:
also, for Oracle,  you only need 11gR2 for the LISTAGG function.
The workhorse of the query is POWERMULTISET which is old, and goes back to 10gR1.
0
fb1990Author Commented:
I think if i post a sample data of what i am tried to do.  I can get all the experts here to help.  Thanks everyone for not given up on me.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Microsoft SQL Server

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.