# How can I permute a multiset?

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.

-
RandomSample does not preserve the structure. –  M.R. Aug 13 '12 at 17:22
For the not-so-bright among us, could you explain how the two sets are permutations of each other and how the positions of the integers remain the same? I don't see theconnection. I see you've been referring answerers to your example, but the example is unhelpful –  rm -rf Aug 13 '12 at 20:31
@r.m. As I understand it the integers should be seen as labels for various items on fixed locations. Duplicate items are possible (and they have corresponding labels). What Mike wants is to swap the labels but not the items. –  Sjoerd C. de Vries Aug 13 '12 at 22:52

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.

-
Another way, much faster still: (RandomSample@Range[0, 1000])[[list + 1]]. –  Oleksandr R. Aug 13 '12 at 18:17
@Oleksandr That method deserves an answer of its own. Why don't you post it? –  Mr.Wizard Jan 13 '14 at 16:21