Michael J. Swart

February 14, 2017

Generate Permutations Fast using SQL

Filed under: Miscelleaneous SQL — Michael J. Swart @ 9:49 am

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.

3 Comments »

  1. 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

  2. […] 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

  3. 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

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress