How to generate Permutations in SQL?

How to generate Permutations in SQL?

SQL interview questions and answers #3


You are planning to go for a summer vacation and finalized the cities you want to visit. But you have not finalized in which order you want to visit them yet.

Write a SQL query to list out all different possible order you can visit these cities.

Note that you don't want to visit the same city again and you don't want to skip any city in your travel plan either.


Expected output: 03-permutations-output.png

Let us create the test data first for the demo.

-- test data
use demo;
if object_id (N'', N'u') is not null 
drop table

create table (
    id int identity(1,1),
    city_name varchar(100)

insert into (city_name) values 

select id, city_name from

Solution: 1

This solution is implemented using the Recursive CTE in SQL Server. If you are using other database engines, you can implement it in similar way.

-- solution 1
declare @total_cities int = (select count(1) from;
;with travel (travel_path, level) as (
    select cast(city_name as varchar(200)), 
    level = 1 
    union all
    select cast(travel.travel_path + ' -> ' + city.city_name as varchar(200)), 
    level = level + 1
    inner join travel on level < @total_cities
    where charindex(city.city_name, travel.travel_path) = 0

id = row_number() over(order by travel_path),
from travel
where level = @total_cities
order by id

Solution: 2

This solution is implemented using a bitwise exclusive or ^ in recursive CTE. I learned this one while I was checking for few other way to implement permutations in SQL.

;with bitmasks as ( 
    select cast(city_name as varchar(max)) as city_name, 
    cast(power(2, row_number() over (order by city_name) - 1) as int) as bitmask 
travel as (
    select city_name as travel_path,
    from bitmasks
    union all
    select p.travel_path + ' -> ' + b.city_name,
    p.bitmask ^ b.bitmask
    from travel p
    join bitmasks b on p.bitmask ^ b.bitmask > p.bitmask
select travel_path
from travel
where bitmask = power(2, (select count(*) from - 1
order by travel_path

If you like this interview question, you may also like these scenario based interview question and answers.

Did you find this article valuable?

Support Rajanand Ilangovan by becoming a sponsor. Any amount is appreciated!