bolov - 7 months ago 52

C++ Question

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

`C`

`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*`

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`

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.