Last active
February 13, 2022 21:19
-
-
Save rajanand/54e7b313a2c9bd4d2ab8d4e4f9b264c0 to your computer and use it in GitHub Desktop.
How to generate permutations in SQL Server? https://blog.rajanand.org/how-to-generate-permutations-in-sql
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*------------------------------------------- | |
2022-02-13 | |
Rajanand Ilangovan | |
https://blog.rajanand.org/how-to-generate-permutations-in-sql | |
How to generate permutations in SQL Server? | |
--------------------------------------------*/ | |
use demo; | |
go | |
-- create test data | |
if object_id (N'dbo.city', N'u') is not null | |
drop table dbo.city | |
go | |
create table dbo.city ( | |
id int identity(1,1), | |
city_name varchar(100) | |
) | |
go | |
insert into dbo.city (city_name) values ('Oslo'),('Helsinki'),('Stockholm'),('Copenhagen') | |
select id, city_name from dbo.city | |
go | |
-- solution | |
declare @total_cities int = (select count(1) from dbo.city); | |
;with travel (travel_path, level) as ( | |
select cast(city_name as varchar(200)), level = 1 from dbo.city | |
union all | |
select cast(travel.travel_path + ' -> ' + city.city_name as varchar(200)) , level + 1 | |
from dbo.city | |
inner join travel on level < @total_cities | |
where charindex(city.city_name, travel.travel_path) = 0 -- to ignore the city name repeats in travel path. | |
) | |
select | |
id = row_number() over(order by travel_path), | |
travel_path | |
from travel | |
where level = @total_cities | |
order by id | |
-- clean up | |
if object_id (N'dbo.city', N'u') is not null | |
drop table dbo.city | |
go |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*------------------------------------------- | |
https://michaeljswart.com/2017/02/generate-permutations-fast-using-sql/ | |
Bitwise exclusive OR operator is used to generate permutations. | |
--------------------------------------------*/ | |
;with city as ( | |
select city_name | |
from ( values ('Oslo'),('Helsinki'),('Stockholm'),('Copenhagen')) city(city_name) | |
), | |
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 | |
from city | |
), | |
travel as ( | |
select city_name as travel_path, | |
bitmask | |
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 city)) - 1 | |
order by travel_path |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment