Permutations.sql

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