random무작위로 시작하기

비고

피셔 - 예이츠 셔플

Knuth 셔플 및 Durstenfeld-Fisher-Yates 셔플이라고도합니다. 이 셔플은 n 요소 배열을 취해 그것을 뒤섞습니다. 이 알고리즘은 셔플 후 배열의 각 순열이 똑같이 적용된다는 점에서 진정으로 무작위입니다.

자바에서 :

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) 시간과 공간을 필요로합니다. 이 방법으로 셔플 된 배열은 요소 당 amortized 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++];
}
 

설치 또는 설정

무작위 설치 또는 설치에 대한 자세한 지침.

PDF - Download random for free