I have a new solution. This one is Recursive CTE but only builds valid solutions instead of all solutions. It will produce the 3.6 million permutations for a 10 character string in 3:02 minutes.

declare @t varchar(10) = 'ABCDEFGHIJ'

;with s(t,n) as (

select substring(@t,1,1),1

union all

select substring(@t,n+1,1),n+1

from s where n<len(@t)

)

,j(t) as (

select cast(t as varchar(10)) from s

union all

select cast(j.t+s.t as varchar(10))

from j,s where patindex('%'+s.t+'%',j.t)=0

)

select t from j where len(t)=len(@t)