random随机入门


备注

本节概述了随机数以及开发人员可能想要使用它的原因。

它还应该随机提及任何大型主题,并链接到相关主题。由于随机文档是新的,您可能需要创建这些相关主题的初始版本。

费雪耶茨洗牌

也被称为Knuth shuffle和Durstenfeld-Fisher-Yates shuffle。这个shuffle需要一组n 元素并将其洗牌。该算法是真正随机的,因为在混洗之后,阵列的每个排列都是同样可能的。

在java中:

public static void shuffle(E[] deck) {

    //From the end, swap each card with a random card from the unswapped portion.
    for(int i = deck.length - 1; i > 0; i--)
    {
        //Pick an element from [0,i], inclusive.
        int chosenCard = (int) (Math.random() * (i + 1));

        E temp = deck[i];
        deck[i] = deck[chosenCard];
        deck[chosenCard] = temp;
    }
}
 

请注意:替换元素必须来自[0,i]包含而不是[0,i]独占:否则,元素保留到位的数组的排列是不可能的,这不是真正随机的。

假设假设随机数采用O(1)生成,则算法就地运行并占用O(n)时间和空间。以这种方式混洗的数组可用于检索每个元素的O(1)摊销时间中的非重复元素。

E[] deck;
int drawIndex;

//Elements are taken from an index that advances.
public E drawUniqueCard()
{
    //Once all cards have been drawn, reshuffle the deck and draw from the top.
    if(drawIndex == deck.length)
    {
        shuffle(deck);
        drawIndex = 0;
    }
    //Pull the next card off the deck.
    return deck[drawIndex++];
}
 

安装或设置

有关获取随机设置或安装的详细说明。