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