Mfcttrf

I was trying to do some code golf, when I created the following algorithm to shuffle a string:

for(;k-->0;y=s,s="")for(var c:y.split(""))s=Math.random()<.5?s+c:c+s;

To explain better what it does, I've recreated it in Python:

import random
str = "Randomize me!"
print('[',str,']',sep='')
temp=""
for _ in range(len(str)): # repeat as many times as the string is long
 for char in str: # take the string's chars and randomly construct a temporary
 temp = temp + char if random.choice([True, False]) else char + temp
 temp, str = "", temp # use the temporary as the basis for the next iteration
print('[',str,']',sep='')

Also, per request, here it is in pseudocode:

SHUFFLE(STR)
 0 TEMP ← ""
 1 LOOP STR.LENGTH TIMES:
 2 FOR EACH CHAR ∈ STR:
 3 IF COIN-FLIP
 4 TEMP = TEMP + CHAR
 5 ELSE
 6 TEMP = CHAR + TEMP
 7 END IF
 8 STR ← TEMP
 9 TEMP ← ""
10 END FOR
11 END LOOP
12 RETURN STR

The output looks randomized to me. However, if you only consider one iteration of the algorithm, the first character put into temp is always str[0]. The second character put into temp on this iteration is always str[1], which must be next to str[0] according to the way characters are appended. Therefore, after one iteration, the probability that the shuffled string has the first character outside of the center is 0, and the probability that it is not adjacent to the second character is 0.

I tried to remedy this problem by repeating the shuffle once for each character in the string. Intuitively, it seems to work, but I can't seem to prove that all permutations of the input string can show up.

So, here's the question: do all permutations of the input string have non-zero probability as output from this shuffle?

Yes. Your algorithm can return all permutations.
You can prove it by fixing any arbitrary permutation $pi$ of the input string str and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of str can match the last $i$ characters of $pi$.

For $i=0$ this is trivial.
For $i>0$: Let $n$ be the lenght of str, $x$ be the character in position $1+n-i$ of $pi$ (indexing positions from $1$), and $j$ be the index of the first occurrence of character $x$ in str with the additional constraint that $j ge i$ (this index always exists by induction hypothesis). A string temp that will satisfy the induction thesis (as it will be assigned to str) can be found as follows:

• copy the first $j-1$ characters from str to temp (by appending them to temp). In particular this copies the first $i-1$ characters of str which, by induction hypothesis, match the last $i-1$ characters of $pi$.


• prepend the $j$-th character of $x$ of str to temp.


• append the remaining $n-j$ characters of str to temp.