随机槽算法 [英] Random slot algorithm

问题描述

我有二维数组.我想随机选择一个位置，并继续这样做，在我最终选择所有位置之前永远不要选择相同的位置两次(当然，最后一次选择没有任何随机性).是否有一个众所周知的算法来做到这一点?我使用的是 C#，但显然这更多的是关于算法而不是任何特定平台.是的，大书"在我的购买清单上:)

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

推荐答案

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

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

这篇关于随机槽算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！