Geek Answers Handbook

How to shuffle an array so that all elements change their place

I need to shuffle the array so that all elements of the array change their location. Given an array of [0,1,2,3] , it would be normal to get [1,0,3,2] or [3,2,0,1] , but not [3,1,2,0] (because 2 remained unchanged). I suppose the algorithm would not be language specific, but just in case I need it in a C ++ program (and I cannot use std::random_shuffle due to an additional requirement).

+6
source share
4 answers
 For each element e If there is an element to the left of e Select a random element r to the left of e swap r and e

This ensures that each value is not in the place where it was run, but does not guarantee that each value changes if duplicated.

+7
source

How about this?

  • Select an array containing numbers from 0 to arrayLength-1
  • Shuffle an array
  • If the array does not have an element whose index is equal to its value, go to step 4; otherwise, repeat step 2.
  • Use shuffled array values ​​as indices for your array.
+4
source

This will not be very random, but you can rotate all the elements at least one position:

 std::rotate(v.begin(), v.begin() + (rand() % v.size() - 1) + 1, v.end());

If v was {1,2,3,4,5,6,7,8,9} at the beginning, then after rotation it will be, for example: {2,3,4,5,6,7,8,9,1} or {3,4,5,6,7,8,9,1,2} etc.

All array elements will change position.

+3
source

I have an idea in my mind, hope this suits your application. You have another container, and this container will be a "map (int, vector (int))". The key element will display the index, and the second element will be a vector that will contain the values ​​that are already in use.

For example, for the first element, you will use the rand function to find which element of the array you should use. If you check the map structure, if this array element was used for this index.

+1
source

More articles:


All Articles