Solved

How to Generate Permutations in SQL

Posted on 2014-07-23
19
254 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 12

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 12

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
 
LVL 24

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 31

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 31

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 31

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
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 12

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 31

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 12

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 12

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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Checking the Alert Log in AWS RDS Oracle can be a pain through their user interface.  I made a script to download the Alert Log, look for errors, and email me the trace files.  In this article I'll describe what I did and share my script.
For both online and offline retail, the cross-channel business is the most recent pattern in the B2C trade space.
Via a live example, show how to restore a database from backup after a simulated disk failure using RMAN.
This video shows how to copy an entire tablespace from one database to another database using Transportable Tablespace functionality.

747 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now