Solved

How to Generate Permutations in SQL

Posted on 2014-07-23
19
410 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
  • 3
  • +3
19 Comments
 
LVL 77

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
Free Webinar: AWS Backup & DR

Join our upcoming webinar with experts from AWS, CloudBerry Lab, and the Town of Edgartown IT to discuss best practices for simplifying online backup management and cutting costs.

 
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 77

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 77

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 74

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 74

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 Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

The Delta outage: 650 cancelled flights, more than 1200 delayed flights, thousands of frustrated customers, tens of millions of dollars in damages – plus untold reputational damage to one of the world’s most trusted airlines. All due to a catastroph…
For both online and offline retail, the cross-channel business is the most recent pattern in the B2C trade space.
This video shows how to recover a database from a user managed backup
Using examples as well as descriptions, and references to Books Online, show the documentation available for datatypes, explain the available data types and show how data can be passed into and out of variables.

726 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