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.

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.

Source (Stackoverflow)