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 :)

You are looking for a random permutation of the set of slots. — dtb
– dtb, Commented Mar 4, 2012 at 19:04

Oliver Charlesworth · Accepted Answer · 2012-03-04 19:04:44Z

5

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

answered Mar 4, 2012 at 19:04

Oliver Charlesworth

274k34 gold badges591 silver badges687 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

L.B · Accepted Answer · 2012-03-04 20:35:00Z

3

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;
    }
}

edited Mar 4, 2012 at 20:35

answered Mar 4, 2012 at 20:20

L.B

116k20 gold badges189 silver badges229 bronze badges

Comments

Richard J. Ross III · Accepted Answer · 2012-03-04 19:40:11Z

1

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.

edited Mar 4, 2012 at 19:40

answered Mar 4, 2012 at 19:05

Richard J. Ross III

55.7k25 gold badges139 silver badges205 bronze badges

4 Comments

Myles McDonnell Over a year ago

Thanks, better than the recursive solution above, but still we will tend to loop more and more as we get toward the end of the set. Perhaps this is just an unavoidable issue?

Richard J. Ross III Over a year ago

@MylesMcDonnell I don't think it's avoidable, and your edit broke the functionality of the code. it is not supposed to be a !, if chosen is set to true, that index is invalid. I have rolled the code back.

Omar Over a year ago

Sorry for messing with your answer ;)

Myles McDonnell Over a year ago

@RichardJ.RossIII Apologies..@Fuex I think we both made the same mistake

Omar · Accepted Answer · 2012-03-04 20:13:38Z

0

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;
}

edited Mar 4, 2012 at 20:13

Omar

16.7k10 gold badges53 silver badges69 bronze badges

answered Mar 4, 2012 at 19:05

Stecenko Ruslan

2931 silver badge3 bronze badges

1 Comment

Myles McDonnell Over a year ago

The problem with this is the closer we get to the end of the set more recursion occurs. It could take a lot of calls to rnd.Next(0,99) to get the last item. Ouch.

Collectives™ on Stack Overflow

Random slot algorithm

4 Answers 4

Comments

Comments

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related