Random slot algorithm

Question

I have two dimensional array. I want to pick a slot at random, and continue to do so never picking the same slot twice until I have finally picked all slots (so nothing random about the last pick of course). Is there a well known algorithm for doing this? I'm using C#, but obviously this is more about algorithms than any particular platform. Yes, 'the big book' is on my purchase list :)

Answer 1

Take a look at the Fisher-Yates shuffle. It's designed to pick a random permutation from a set.

Answer 2

Using the Fisher-Yates shuffle algorithm as mentioned before (in O(n) time)

int X = 3;  int Y = 4;
int[] array = new int[X * Y];

for (int i = 0; i < array.Length; i++) array[i] = i;
FisherYatesShuffle(array);

var randomSlots = array.Select((i,j) => new {x=array[j]%X , y=array[j]/X })
                       .ToArray();

---

public static void FisherYatesShuffle<T>(T[] array)
{
    Random r = new Random();
    for (int i = array.Length - 1; i > 0; i--)
    {
        int j = r.Next(0, i + 1);
        T temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
}

Answer 3

Assuming your array is like this:

Random rand = new Random();

object[,] array = new object[width,height];
bool[,] chosen = new bool[width,height];

int i, j;
do
{
    i = rand.Next(width);
    j = rand.Next(height);
} while (chosen[i,j]);

chosen[i,j] = true;
object current = array[i,j];

This should work fine.

Answer 4

I did this for numbers

list<int> PastList=new PastList<int>();
private void Choоse()
{
   int i = Recurs();
   PastList.Add(i);
}

private int Recurs()
{
   int i;

   i = rnd.Next(0, 99);
   if (PastList.Contains(i))
   {
       i = Recurs();
   }

   return i;
}