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]


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.

  • $\begingroup$ RandomSample does not preserve the structure. $\endgroup$
    – M.R.
    Commented Aug 13, 2012 at 17:22
  • $\begingroup$ 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 $\endgroup$
    – rm -rf
    Commented Aug 13, 2012 at 20:31
  • $\begingroup$ @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. $\endgroup$ Commented Aug 13, 2012 at 22:52

1 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.

  • 3
    $\begingroup$ Another way, much faster still: (RandomSample@Range[0, 1000])[[list + 1]]. $\endgroup$ Commented Aug 13, 2012 at 18:17
  • $\begingroup$ @Oleksandr That method deserves an answer of its own. Why don't you post it? $\endgroup$
    – Mr.Wizard
    Commented Jan 13, 2014 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.