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 (
from s where n<len(@t)
,j(t) as (
select cast(t as varchar(10)) from s
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)