Skip to content

Instantly share code, notes, and snippets.

/Permutations.sql

Created Feb 14, 2017
Embed
What would you like to do?
------------------------------------------------------------
-- Alternative solution
------------------------------------------------------------
IF OBJECT_ID('tempdb..#letters') IS NOT NULL DROP TABLE #letters
CREATE TABLE #letters (letter CHAR(1) NOT NULL)
INSERT INTO #letters (letter) VALUES ('a'), ('b'), ('c'), ('d'), ('e'), ('f'), ('g'), ('h'), ('i')
IF OBJECT_ID('tempdb..#numbers') IS NOT NULL DROP TABLE #numbers
CREATE TABLE #numbers (n INT NOT NULL)
INSERT INTO #numbers (n) SELECT ROW_NUMBER() OVER (ORDER BY (SELECT 0)) FROM #letters
IF OBJECT_ID('dbo.fringePermutations') IS NOT NULL DROP TABLE dbo.fringePermutations
IF OBJECT_ID('dbo.permutations') IS NOT NULL DROP TABLE dbo.permutations
/* SELECT STRING_AGG(letter,'') FROM #letters */
SELECT '' AS permutation, 'abcdefghi' AS remaining INTO dbo.permutations
WHILE EXISTS (SELECT * FROM #numbers)
BEGIN
SELECT addChar.permutation, addChar.remaining
INTO dbo.fringePermutations
FROM dbo.permutations p
CROSS APPLY (
SELECT p.permutation + SUBSTRING(p.remaining, n.n, 1) AS permutation, STUFF(p.remaining, n.n, 1, '') AS remaining
FROM #numbers n
) addChar;
DROP TABLE dbo.permutations;
EXEC sp_rename 'dbo.fringePermutations', 'permutations';
WITH N AS (SELECT TOP 1 * FROM #numbers ORDER BY n DESC) DELETE FROM N;
END
GO
-- Confirm results
SELECT COUNT(*), COUNT(DISTINCT permutation), MIN(LEN(permutation)), MAX(LEN(permutation)) FROM dbo.permutations
-- 362880 362880 9 9
GO
------------------------------------------------------------
-- Compare against the original solution
------------------------------------------------------------
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
into #permutations
from Permutations
where bitmask = power(2, (select count(*) from Letters)) - 1
-- Confirm all results match
SELECT COUNT(*)
FROM dbo.permutations p1
FULL OUTER JOIN #permutations p2
ON p1.permutation = p2.permutation
-- 362880
GO
------------------------------
-- Cleanup
------------------------------
DROP TABLE dbo.permutations;
GO
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.