CODEWITHSUNDEEP
c++arraysmultidimensional-arraystlshuffle
bolov
bolov

Reputation: 75697

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.

Upvotes: 2

Views: 1180

Answers (3)

Ami Tavory
Ami Tavory

Reputation: 76297

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.

Upvotes: 3

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

you can choose a bijective function between an integer (your 1-D) index and the (i,j) pair, so this will be the way of treating your matrix as 1-D array. This is called a 'numbering scheme'.

Something like:

oneDindex(rowIndex,colIndex)=colIndex*rowCount+rowIndex;

inverse transform 

rowIndex=oneDIndex % rowCount

colIndex=oneDIndex / rowCount;

So, you pick two 1D indexes at random in [0, rowCount*colCount) that you want exchanged, get their (rowIndex, colIndex) by the inverse transform and exchange them. Repeat until satisfied.

Upvotes: 1

gabbar0x
gabbar0x

Reputation: 4246

Is there a simple way to fill and then shuffle the 2D array without creating a 1D array

Sure. Assuming you have filled the array, to shuffle it, why not randomly generate i1 ,i2, j1, j2 where i and j are the limits of the rows and columns. Now interchange the values at these indices. Do this say 0.5 x no.of.rows x no.of.cols , which is just a very rough figure. Essentially feel free to randomize it as much as you like. Anything less than 10^8 should be fine.

If you are worried generating duplicate pairs(which shouldn't really be a problem with larger matrices) you can maintain an std::set<pair<int, int> > which stores the indices generated. Whenever you generate i and j, check if {i, j} exists. If it does, regenerate it.

Upvotes: 1

Related Questions