2

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.

Community
  • 1
  • 1
bolov
  • 72,283
  • 15
  • 145
  • 224
  • `Is there a simple way to fill and then shuffle the 2D array without creating a 1D array`. 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 2000 times and it should be pretty alright – gabbar0x Sep 19 '16 at 08:03
  • @bholagabbar ok... I think I would need to make sure not to generate duplicate pairs – bolov Sep 19 '16 at 08:05
  • Naah that's alright. i and j being the same, assuming your matrix is sufficiently large will occur very few number of times – gabbar0x Sep 19 '16 at 08:06
  • @bholagabbar oh.. sry now I see what you are saying. Yeah, I guess it would work. (the matrix is small) – bolov Sep 19 '16 at 08:08
  • If you really want, you can maintain two `std::set`s which store already encountered `i` and `j`. If both of them exist in both the sets, regenerate the pair – gabbar0x Sep 19 '16 at 08:08
  • @bholagabbar if (i,k) and (p,j) have been added, then your set solution will say don't add (i,j) which is wrong – Rohith R Sep 19 '16 at 08:11
  • no, no, I misunderstood the firs time. Duplicates are a non-issue actually, as it will be repeated a significant amount of times. – bolov Sep 19 '16 at 08:12
  • I've put my comments as an answer. Hope this idea works for you! – gabbar0x Sep 19 '16 at 08:13
  • @bolov you are right about the duplicates part. You can maintain an `std::set >` to store the duplicate indices. – gabbar0x Sep 19 '16 at 08:18

3 Answers3

3

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.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
1

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.

gabbar0x
  • 4,046
  • 5
  • 31
  • 51
1

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.

Adrian Colomitchi
  • 3,974
  • 1
  • 14
  • 23
  • I know about this function. But I would need to create a iterator-wrapper object. If you ever tried to create an iterator class in C++ you know that is far from simple. – bolov Sep 19 '16 at 08:24
  • Do you really need to use std::shuffle? You said you have a C array that need shuffling - why don't you code your own shuffle algo on top of that? It will certainly be easier than to write an iterator. Note: the 'why' question is really a question, not a critique in disguise, I am interested in an answer. – Adrian Colomitchi Sep 19 '16 at 08:39
  • Before you added the last paragraph I thought you meant to use these transformations in order to use `std::shuffle`. You are right, I don't need to use `std::shuffle`. Your solution is OK. – bolov Sep 19 '16 at 08:57