Questo shuffle ha una probabilità diversa da zero per tutte le permutazioni?

Question

Stavo cercando di fare un po 'di golf di codice, quando ho creato il seguente algoritmo per mescolare una stringa:

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

Per spiegare meglio cosa fa, l'ho ricreato 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='')

Inoltre, per richiesta, qui è in pseudocodice:

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

L'output mi sembra randomizzato. Tuttavia, se si considera solo un'iterazione dell'algoritmo, il primo personaggio inserito in temp è sempre str[0]. Il secondo personaggio messo in temp Su questa iterazione è sempre str[1], quale dovere essere accanto a str[0] Secondo il modo in cui i personaggi vengono aggiunti. Pertanto, dopo un'iterazione, la probabilità che la corda mescolata abbia il primo carattere al di fuori del centro è 0 e la probabilità che non sia adiacente al secondo carattere è 0.
Ho provato a porre rimedio a questo problema ripetendo lo shuffle una volta per ogni personaggio nella stringa. Intuitivamente, sembra funzionare, ma non riesco a dimostrare che tutte le permutazioni della stringa di input possano visualizzare.

Quindi, ecco la domanda: tutte le permutazioni della stringa di input hanno una probabilità diversa da zero come output da questo shuffle?