Source code in the icon programming language

# every !t :=: ?t    # Uncomment to get a random best shuffling


procedure main(args)
    while scram := bestShuffle(line := read()) do
        write(line," -> ",scram," (",unchanged(line,scram),")")
end

procedure bestShuffle(s)
    t := s
    # every !t :=: ?t    # Uncomment to get a random best shuffling
    every i := 1 to *t do
        every j := (1 to i-1) | (i+1 to *t) do
           if (t[i] ~== s[j]) & (s[i] ~== t[j]) then break t[i] :=: t[j]
    return t
end        

procedure unchanged(s1,s2)      # Number of unchanged elements
    every (count := 0) +:= (s1[i := 1 to *s1] == s2[i], 1)
    return count
end