bolov bolov - 11 months ago 67
C++ Question

Shuffling a matrix

I need to randomly fill a matrix with a given number of a certain value. (For some reason I have a

2D array). The simple solution I found was to interpret the 2D array as a 1D array: (please ignore the hard coded constants and ad hoc random objects):

int m[10][10] = {};

std::fill_n(&m[0][0], 24, -1);
std::shuffle(&m[0][0], &m[0][0] + 100, std::mt19937{std::random_device{}()});

But this seems to be controversial as whether or not it is Undefined Behavior:

Is it legal to access a bidimensional array as if it where a one-dimensional one?

May I treat a 2D array as a contiguous 1D array?

The gist is that even if the underlying data is guaranteed to be contiguous without padding between rows, the indexing scheme or incrementing the
pointer outside of the first row is invalid.

So I am searching for an alternate safe method. Is there a simple way to fill and then shuffle the 2D array without creating a 1D array and then copying it in the matrix?

Note: the rest of the matrix is all
so it is not needed to preserve those cells.

Answer Source

Say your 2d array is of dimensions m X n, it is initialized, and you'd like to do an in-place random shuffle.

It is very easy to modify the Durstenfeld variant of the Fisher-Yates Shuffling algorithm for this. Following is the pseudocode:

for i = m * n - 1 downto 1
    j = random integer in the range [0, i] (both inclusive)
    swap(a[i / n][i % n], a[j / n][j % n])

This is essentially the original algorithm, treating the array as 1d. Whenever indices i and j are chosen, though, the translation to row + column is made for each before acting on it.