Consider a recursive function called permuteR $($string$,$ position$)$ that returns each reordering of the letters in a string.

def swap$(st,1,r)$ :

st $=$ list$($st$)$

st $1,$st $[r]=st[r],$ st$[1]$

return $\text{'}\text{'}.$join$($st$)$

def permuteR$($st$,l=0$ :

if len$(st)==1$ :

return $[$st$]$

$L=[]$

for $i$ in range$(1,$ len$($st$))$:

st $=$swap$(st,i,l)$

L $+=$ permuteR$($st$,$ l$+1)$

st $=$swap$(st,i,1)$

return $L$

print$($permuteR$("123"))$

# $[\text{'}123\text{'},\text{'}132\text{'},\text{'}213\text{'},\text{'}231\text{'},\text{'}321\text{'},\text{'}312\text{'}]$

What is the recurrence relation of pe rmuteR?

$T(n)=K+(n-1)**T(n-1)$

$T(n)=K+T(n-1)$

$T(n)=K+T(\frac{n}{log(n)})$

$T(n)=K+T((n+1)log(n))$