If you google “generating permutations using SQL”, you get thousands of hits. It’s an interesting problem if not very useful.

I wrote a solution recently and thought I’d share it. If you’re keen, try tackling it yourself before moving on.

### My Solution

Notice the use of recursive CTEs as well as bitmasks and the exclusive or operator (^).

with Letters as ( select letter from ( values ('a'), ('b'), ('c'), ('d'), ('e'), ('f'), ('g'), ('h'), ('i') ) l(letter) ), Bitmasks as ( select cast(letter as varchar(max)) as letter, cast(power(2, row_number() over (order by letter) - 1) as int) as bitmask from Letters ), Permutations as ( select letter as permutation, bitmask from Bitmasks union all select p.permutation + b.letter, p.bitmask ^ b.bitmask from Permutations p join Bitmasks b on p.bitmask ^ b.bitmask > p.bitmask ) select permutation from Permutations where bitmask = power(2, (select count(*) from Letters)) - 1 |

362880 rows (9!) in less than ten seconds. Let me know what you come up with.

Interesting problem. I had a few ideas that turned out to not be very good, but came up with one that might work if you’re willing to assume that each value is a single character (e.g., a letter or digit). This completes in about a second for me:

https://gist.github.com/anonymous/73a7a950fc6ecb415676221f8bcbe35f

The primary idea is to maintain a pool of remaining letters to be added at each step, and to add each letter from that pool in order to generate a new partial permutation with a new (smaller-by-one) remaining pool of letters to add. I think the solution could be extended to multi-character values, but it would get a lot uglier.

Comment by Geoff Patterson — February 14, 2017 @ 2:07 pm

[…] Michael J. Swart uses a recursive common table expression and bit shifting to build a full set of pe…: […]

Pingback by Generating SQL Permutations – Curated SQL — February 15, 2017 @ 8:05 am

Well done Geoff, When I bumped up your solution to 11 letters, it really shows your improvement, 60 seconds versus my 10 minutes and counting

Comment by Michael J. Swart — February 22, 2017 @ 9:08 am