随机时隙算法

Question

我有一个二维数组。我想随机挑选一个插槽，并继续这样做，在我最终挑选完所有插槽之前，决不会挑选相同的插槽两次(所以最后一次挑选当然不是随机的)。有没有一个广为人知的算法来做这件事？我使用的是C#，但显然这更多的是关于算法，而不是任何特定的平台。是的，“大书”在我的购买清单上:)

Answer 1

使用前面提到的Fisher-Yates shuffle算法( O(n)时间)

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 2

看一看。它被设计成从一个集合中选择一个随机的排列。

Answer 3

假设你的数组是这样的：

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

这应该可以很好地工作。