Ce remaniement a-t-il une probabilité non nulle pour toutes les permutations?

Question

J'essayais de faire du golf de code, lorsque j'ai créé l'algorithme suivant pour mélanger une chaîne:

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

Pour mieux expliquer ce qu'il fait, je l'ai recréé à 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='')

En outre, par demande, ici, c'est en 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     END FOR
 9     STR ← TEMP
10     TEMP ← ""
11 END LOOP
12 RETURN STR

La sortie me semble randomisée. Cependant, si vous ne considérez qu'une seule itération de l'algorithme, le premier personnage mis dans temp est toujours str[0]. Le deuxième personnage mis dans temp sur cette itération est toujours str[1], qui devoir être à côté de str[0] Selon la façon dont les personnages sont annexés. Par conséquent, après une itération, la probabilité que la chaîne mélangée ait le premier caractère en dehors du centre est de 0, et la probabilité qu'elle ne soit pas adjacente au deuxième caractère est 0.
J'ai essayé de remédier à ce problème en répétant le shuffle une fois pour chaque personnage de la chaîne. Intuitivement, cela semble fonctionner, mais je n'arrive pas à prouver que toutes les permutations de la chaîne d'entrée peuvent apparaître.

Alors, voici la question: toutes les permutations de la chaîne d'entrée ont-elles une probabilité non nulle en tant que sortie de ce shuffle?