I was trying to do some code golf, when I created the following algorithm to shuffle a string:
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 END FOR 9 STR ← TEMP 10 TEMP ← "" 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. The second character put into
temp on this iteration is always
str, which must be next to
str 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?