Randomly filling a 2d boolean array with equal amounts of both values

Question

I'm trying to find a way to fill a 2d array of length n with boolean values randomly. The array must have an equal amount of each value if n is even, and if n is odd the extra value must be the same boolean each and every time (doesn't matter which one). Any tips on how to do this in Java? I'm currently shuffling arrays that I make with equal amounts of both values, but this isn't truly random because there will always be n/2 (or n/2+1 and n/2-1 for the odd ns) of each value.

Any advice?

You said that there always have to be n/2 of each value (or +1 to one of them for odd *n*), so how's that a problem? — user253751, Feb 03 '15 at 23:37
And if you want to fill an array with "truly random" boolean values, then you aren't guaranteed to get the same number of each, because that's how randomness works. — user253751, Feb 03 '15 at 23:38
There always needs to be an equal amount of each, but they need to be distributed randomly. — Brandon Slaght, Feb 03 '15 at 23:40
Your current approach isn't actually bad, but it's trickier with 2D arrays. the best solution would probably be trying to adapt the Fisher-Yates shuffle to 2D arrays. — Louis Wasserman, Feb 03 '15 at 23:40
If you require a certain quantity of each value, set them and then shuffle the array. http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array — Kevin Krumwiede, Feb 03 '15 at 23:40
Kevin, I am currently doing that but it only works for one dimension and I can't figure out how to adapt it to two: I can't shuffle between the arrays in the 2nd dimension — Brandon Slaght, Feb 03 '15 at 23:43

score 1 · Answer 1 · answered Feb 03 '15 at 23:42

1

Given your requirements, filling the array with the amount you need, then shuffling it, is a good solution.

Make sure to use a truly random shuffling algorithm, such as the Fisher-Yates shuffle, not the "swap a random pair a bunch of times" method. If you're using Collections.shuffle or similar, you don't need to worry about this.

answered Feb 03 '15 at 23:42

user253751

57,427
7
48
90

I'm currently using the Fisher-Yates algorithm, but how would I adapt this to two dimensions? – Brandon Slaght Feb 03 '15 at 23:45
@user2943867 Just pretend your 2D array is a long 1D array - every time the algorithm says `array[index]`, you use `array[index / height][index % height]` instead (where `height` is the length of the second dimension) - and if the algorithm says "the length of the array", then you use the total number of elements (`width * height`) – user253751 Feb 03 '15 at 23:49

score 0 · Accepted Answer · answered Feb 03 '15 at 23:44

Adapting the Fisher-Yates shuffle to a 2D array is probably the simplest approach.

 boolean[][] array = new boolean[rows][cols];
 boolean alternating = false;
 Random random = new Random();
 for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      int k = random.nextInt(i * cols + j + 1);
      int swapRow = k / cols;
      int swapCol = k % cols;
      boolean tmp = array[swapRow][swapCol];
      array[swapRow][swapCol] = alternating;
      array[i][j] = tmp;
      alternating = !alternating;
    }
 }

This is pretty much a verbatim implementation of http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm , except that we're filling the array as we go with falses and trues.

score 0 · Answer 3 · answered Feb 03 '15 at 23:46

A different approach might be to randomise the position you are placing the next value rather than the value itself. You know ahead of time exactly how many of each value you are placing.

Something like:

List<Integer> indicesList = IntStream.range(0, n * n).collect(Collectors.toList());
Collections.shuffle(indicesList);
indicesList.stream().forEach(n -> array[n % size][n / size] = (n % 2 == 0));

By my understanding that should give you completely random placement of your values and an equal number of each.

score 0 · Answer 4 · answered Feb 04 '15 at 00:27

Here's a real simple solution a coworker came up with. It looks to me like it would work and be truly random (please let me know if not, I have terrible intuition about that kind of thing), although it's definitely ugly. Would be pretty efficient compared to a shuffle I imagine.

public boolean[][] generateRandom2dBooleanArray(int length) {
    int numFalses = (length*length)/2;
    int numTrues = (length*length)/2;
    if ((length*length)%2!=0) numTrues++; 

    boolean[][] array = new boolean[length][length];

    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {

            if (Math.random() > 0.5) {//Or is it >= 0.5?  
                    if (numTrues >= 0) {
                        array[i][j] = true;
                        numTrues--;
                    } else {
                        //Since boolean arrays are false by default, you could probably just break here to get the right anser, but...
                        array[i][j] = false;
                        numFalses--;
                    }
                } else {
                    if (numFalses >= 0) {
                        array[i][j] = false;
                        numFalses--;
                    } else {
                        array[i][j] = true;
                        numTrues--;
                    }
                }
            }
        }
    }

    return array;
}

Randomly filling a 2d boolean array with equal amounts of both values

4 Answers4