bolov bolov - 2 months ago 14
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

C
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
&m[0][0]
int*
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
0
so it is not needed to preserve those cells.

Answer

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.

Comments