Here are two ways of solving this issue, the first one; called BruteForceRandomImplementation is easy to implement and understand but quite slow once you attempt to mark a very large number of locations with 1s due to it's brute-force like usage of Random till it fills enough locations.
/// <summary>
/// This method uses a random based algorithm to create a two-dimensional array of [height, width]
/// with exactly locationsToFind locations set to 1.
/// </summary>
/// <param name="height"></param>
/// <param name="width"></param>
/// <param name="locationsToFind"></param>
/// <returns></returns>
public int[,] BruteForceRandomImplementation(int height, int width, int locationsToFind)
{
var random = new Random();
locationsToFind = LimitLocationsToFindToMaxLocations(height, width, locationsToFind);
// Create our two-dimensional array.
var map = new int[height, width];
int locationsFound = 0;
// Randomly set positons to 1 untill we have set locationsToFind locations to 1.
while (locationsFound < locationsToFind)
{
// Get a random Y location - limit the max value to our height - 1.
var randomY = random.Next(height);
// Get a random X location - limit the max value to our width - 1.
var randomX = random.Next(width);
// Find another random location if this location is already set to 1.
if (map[randomY, randomX] == 1)
continue;
// Otherwise set our location to 1 and increment the number of locations we've found.
map[randomY, randomX] = 1;
locationsFound += 1;
}
return map;
}
With the following helper method to keep our locationsToFind range sane:
/// <summary>
/// Limits the locationsToFind variable to the maximum available locations. This avoids attempting to
/// mark more locations than are available for our width and height.
/// </summary>
/// <param name="height"></param>
/// <param name="width"></param>
/// <param name="locationsToFind"></param>
/// <returns></returns>
public int LimitLocationsToFindToMaxLocations(int height, int width, int locationsToFind)
{
return Math.Min(locationsToFind, height * width);
}
My second implementation called ShuffleImplementation is a lot faster when you are marking large numbers of unique locations. It creates a one-dimensional array, fills this with enough 1s to satisify your needs then shuffles this array using the Fisher-Yates shuffle to finally proceed to expand this one-dimensional array into a two-dimensional one:
/// <summary>
/// This method uses a shuffle based algorithm to create a two-dimensional array of [height, width]
/// with exactly locationsToFind locations set to 1.
/// </summary>
/// <param name="height"></param>
/// <param name="width"></param>
/// <param name="locationsToFind"></param>
/// <returns></returns>
public int[,] ShuffleImplementation(int height, int width, int locationsToFind)
{
locationsToFind = LimitLocationsToFindToMaxLocations(height, width, locationsToFind);
// Create a 1 dimensional array large enough to contain all our values.
var array = new int[height * width];
// Set locationToFind locations to 1.
for (int location = 0; location < locationsToFind; location++)
array[location] = 1;
// Shuffle our array.
Shuffle(array);
// Now let's create our two-dimensional array.
var map = new int[height, width];
int index = 0;
// Expand our one-dimensional array into a two-dimensional one.
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
map[y, x] = array[index];
index++;
}
}
return map;
}
/// <summary>
/// Shuffles a one-dimensional array using the Fisher-Yates shuffle.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
public static void Shuffle<T>(T[] array)
{
var random = new Random();
for (int i = array.Length - 1; i > 0; i--)
{
int n = random.Next(i + 1);
Swap(ref array[i], ref array[n]);
}
}
/// <summary>
/// Swaps two values around.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="valueA"></param>
/// <param name="valueB"></param>
public static void Swap<T>(ref T valueA, ref T valueB)
{
T tempValue = valueA;
valueA = valueB;
valueB = tempValue;
}
Usage:
var map = BruteForceRandomImplementation(7, 3, 5);
Or:
var map = ShuffleImplementation(7, 3, 5);
Depending on which one you want to use. For a good example of the performance difference between the two, try:
int width = 1000;
int height = 1000;
int locationsToFind = (width * height) - 1;
var stopwatch = new Stopwatch();
stopwatch.Start();
BruteForceRandomImplementation(height, width, locationsToFind);
stopwatch.Stop();
Console.WriteLine(string.Format("BruteForceRandomImplementation took {0}ms", stopwatch.ElapsedMilliseconds));
stopwatch.Restart();
ShuffleImplementation(height, width, locationsToFind);
stopwatch.Stop();
Console.WriteLine(string.Format("ShuffleImplementation took {0}ms", stopwatch.ElapsedMilliseconds));
On my laptop BruteForceRandomImplementation took 1205ms and ShuffleImplementation took 67ms or nearly 18x faster.
