How can I permute a multiset?

Question

I have a multiset {1, 3, 3, 1, 2} and would like to randomly permute the classes like so: {2, 1, 1, 2, 3} or {3, 2, 2, 3, 1}, what is the simplest and most efficient way to do this?

In reality the input set would be like RandomInteger[1000, 1000000]

Edit

The tricky part of this question is that the positions of the same integers must remain the same! Only the representatives are permuted, but the positions of the classes of integers need to remain the same.

Answer 1

You could do something like this:

list = RandomInteger[1000,1000000];
rules = Dispatch@Thread[Range[0, 1000] -> RandomSample[Range[0, 1000]]];
newlist = list /. rules; 

Thread creates rules for the integers from 1-1000 to a random permutation of the same integers. /.then does the replacement.

Edit: I added Dispatch as per Oleksandr R.'s comment. It cuts the time on my machine from 8.3 seconds to 0.2 seconds.