CODEWITHSUNDEEP
c++randomshuffle
Nick
Nick

Reputation: 3435

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

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

Upvotes: 8

Views: 4501

Answers (4)

Mooing Duck
Mooing Duck

Reputation: 66922

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 guarantees that each value isn't in the position that it started, but doesn't guarantee that each value changes if there's duplicates.

BeeOnRope notes that though simple, this is flawed. Given the list [0,1,2,3], this algorithm cannot produce the output [1,0,3,2].

Upvotes: 4

piokuc
piokuc

Reputation: 26184

It's not going to 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 elements of the array will change position.

Upvotes: 2

Boris Šuška
Boris Šuška

Reputation: 1794

What about this?

  1. Allocate an array which contains numbers from 0 to arrayLength-1
  2. Shuffle the array
  3. If there is no element in array whose index equals its value, continue to step 4; otherwise repeat from step 2.
  4. Use shuffled array values as indexes for your array.

Upvotes: 8

Kadir Erdem Demir
Kadir Erdem Demir

Reputation: 3595

I kind of have a idea in my mind hope it fits your application. Have one more container and this container will be a "map(int,vector(int))" . The key element will show index and the second element the vector will hold the already used values.

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

Upvotes: 1

Related Questions