Solved

How to Generate Permutations in SQL

Posted on 2014-07-23
19
312 Views
Last Modified: 2014-12-07
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,
0
Comment
Question by:fb1990
  • 5
  • 4
  • 3
  • +3
19 Comments
 
LVL 76

Expert Comment

by:slightwv (䄆 Netminder)
ID: 40215923
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
 
LVL 13

Expert Comment

by:Koen Van Wielink
ID: 40215985
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
 
LVL 13

Expert Comment

by:Koen Van Wielink
ID: 40216043
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
VMware Disaster Recovery and Data Protection

In this expert guide, you’ll learn about the components of a Modern Data Center. You will use cases for the value-added capabilities of Veeam®, including combining backup and replication for VMware disaster recovery and using replication for data center migration.

 
LVL 25

Expert Comment

by:Tomas Helgi Johannsson
ID: 40237839
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
 
LVL 32

Expert Comment

by:awking00
ID: 40239525
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
 
LVL 32

Expert Comment

by:awking00
ID: 40241041
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
 
LVL 32

Expert Comment

by:awking00
ID: 40241043
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
 
LVL 76

Expert Comment

by:slightwv (䄆 Netminder)
ID: 40241050
awking00,

Seems that produces the same output as my post above but uses pl/sql.  PL/SQL is unnecessary.
0
 
LVL 13

Expert Comment

by:Koen Van Wielink
ID: 40241058
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
 
LVL 32

Expert Comment

by:awking00
ID: 40241123
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
 
LVL 13

Expert Comment

by:Koen Van Wielink
ID: 40241304
That's how I understood it. Seems the asker has disappeared though...
0
 
LVL 1

Author Comment

by:fb1990
ID: 40242583
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
 
LVL 76

Expert Comment

by:slightwv (䄆 Netminder)
ID: 40242600
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
 
LVL 13

Expert Comment

by:Koen Van Wielink
ID: 40242715
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
 
LVL 73

Accepted Solution

by:
sdstuber earned 500 total points
ID: 40243766
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
 
LVL 73

Expert Comment

by:sdstuber
ID: 40243812
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
 
LVL 1

Author Comment

by:fb1990
ID: 40244502
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

Featured Post

Migrating Your Company's PCs

To keep pace with competitors, businesses must keep employees productive, and that means providing them with the latest technology. This document provides the tips and tricks you need to help you migrate an outdated PC fleet to new desktops, laptops, and tablets.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Why is this different from all of the other step by step guides?  Because I make a living as a DBA and not as a writer and I lived through this experience. Defining the name: When I talk to people they say different names on this subject stuff l…
From implementing a password expiration date, to datatype conversions and file export options, these are some useful settings I've found in Jasper Server.
This video shows how to Export data from an Oracle database using the Datapump Export Utility.  The corresponding Datapump Import utility is also discussed and demonstrated.
Viewers will learn how to use the SELECT statement in SQL to return specific rows and columns, with various degrees of sorting and limits in place.

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question