CODEWITHSUNDEEP
javarandom
user1086516
user1086516

Reputation: 877

Creating an even amount of randomness in an array

Let's say that you have an arbitrarily large sized two-dimensional array with an even amount of items in it. Let's also assume for clarity that you can only choose between two things to put as a given item in the array. How would you go about putting a random choice at a given index in the array but once the array is filled you have an even split among the two choices?

If there are any answers with code, Java is preferred but other languages are fine as well.

Upvotes: 2

Views: 131

Answers (5)

Salain
Salain

Reputation: 752

It doesn't sound like your requirements for randomness are very strict, but I thought I'd contribute some more thoughts for anyone who may benefit from them.

You're basically asking for a pseudorandom binary sequence, and the most popular one I know of is the maximum length sequence. This uses a register of n bits along with a linear feedback shift register to define a periodic series of 1's and 0's that has a perfectly flat frequency spectrum. At least it is perfectly flat within certain bounds, determined by the sequence's period (2^n-1 bits).

What does that mean? Basically it means that the sequence is guaranteed to be maximally random across all shifts (and therefore frequencies) if its full length is used. When compared to an equal length sequence of numbers generated from a random number generator, it will contain MORE randomness per length than your typical randomly generated sequence.

It is for this reason that it is used to determine impulse functions in white noise analysis of systems, especially when experiment time is valuable and higher order cross effects are less important. Because the sequence is random relative to all shifts of itself, its auto-correlation is a perfect delta function (aside from qualifiers indicated above) so the stimulus does not contaminate the cross correlation between stimulus and response.

I don't really know what your application for this matrix is, but if it simply needs to "appear" random then this would do that very effectively. In terms of being balanced, 1's vs 0's, the sequence is guaranteed to have exactly one more 1 than 0. Therefore if you're trying to create a grid of 2^n, you would be guaranteed to get the correct result by tacking a 0 onto the end.

So an m-sequence is more random than anything you'll generate using a random number generator and it has a defined number of 0's and 1's. However, it doesn't allow for unqualified generation of 2d matrices of arbitrary size - only those where the total number of elements in the grid is a power of 2.

Upvotes: 0

Oktalist
Oktalist

Reputation: 14714

Pseudo-code:

int trues_remaining = size / 2;
int falses_remaining = size / 2;

while (trues_remaining + falses_remaining > 0)
{
  if (trues_remaining > 0)
  {
    if (falses_remaining > 0)
      array.push(getRandomBool());
    else
      array.push(true);
  }
  else
    array.push(false);
}

Doesn't really scale to more than two values, though. How about:

assoc_array = { 1 = 4, 2 = 4, 3 = 4, 4 = 4 };

while (! assoc_array.isEmpty())
{
  int index = rand(assoc_array.getNumberOfKeys());
  int n = assoc_array.getKeyAtIndex(index);

  array.push(n);

  assoc_array[n]--;
  if (assoc_array[n] <= 0) assoc_array.deleteKey(n);
}

EDIT: just noticed you asked for a two-dimensional array. Well it should be easy to adapt this approach to n-dimensional.

EDIT2: from your comment above, "school yard pick" is a great name for this.

Upvotes: 0

obataku
obataku

Reputation: 29646

The below creates a List<T> the size of the area of the matrix, and fills it half with the first choice (spaces[0]) and half with the second (spaces[1]). Afterward, it applies a shuffle (namely Fisher-Yates, via Collections.shuffle) and begins to fill the matrix with these values.

static <T> void fill(final T[][] matrix, final T... space) {
  final int w = matrix.length;
  final int h = matrix[0].length;
  final int area = w * h;
  final List<T> sample = new ArrayList<T>(area);
  final int half = area >> 1;
  sample.addAll(Collections.nCopies(half, space[0]));
  sample.addAll(Collections.nCopies(half, space[1]));
  Collections.shuffle(sample);
  final Iterator<T> cursor = sample.iterator();
  for (int x = w - 1; x >= 0; --x) {
    final T[] column = matrix[x];
    for (int y = h - 1; y >= 0; --y) {
      column[y] = cursor.next();
    }
  }
}

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726559

A 2-D A[M,N] array can be mapped to a vector V[M*N] (you can use a row-major or a column-major order to do the mapping).

Start with a vector V[M*N]. Fill its first half with the first choice, and the second half of the array with the second choice object. Run a Fisher-Yates shuffle, and convert the shuffled array to a 2-D array. The array is now filled with elements that are evenly split among the two choices, and the choices at each particular index are random.

Upvotes: 1

James Montagne
James Montagne

Reputation: 78650

You could basically think about it in the opposite way. Rather than deciding for a given index, which value to put in it, you could select n/2 elements from the array and place the first value in them. Then place the 2nd value in the other n/2.

Upvotes: 1

Related Questions