Tworzenie liczb losowych bez duplikatów

W tym przypadku MAX to tylko 5, więc mógłbym sprawdzić duplikaty jeden po drugim, ale jak mogę to zrobić w prostszy sposób? Na przykład, co się stanie, jeśli MAX ma wartość 20? Dzięki.

int MAX = 5;

for (i = 1 , i <= MAX; i++)
{
        drawNum[1] = (int)(Math.random()*MAX)+1;

        while (drawNum[2] == drawNum[1])
        {
             drawNum[2] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )
        {
             drawNum[3] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )
        {
             drawNum[4] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[5] == drawNum[1]) ||
               (drawNum[5] == drawNum[2]) ||
               (drawNum[5] == drawNum[3]) ||
               (drawNum[5] == drawNum[4]) )
        {
             drawNum[5] = (int)(Math.random()*MAX)+1;
        }

}

Najprostszym sposobem byłoby utworzenie listy możliwych liczb (1..20 lub cokolwiek innego), a następnie przetasowanie ich Collections.shuffle. Następnie weź dowolną liczbę elementów. Jest to świetne, jeśli twój zasięg jest równy liczbie elementów, których potrzebujesz na końcu (np. Do tasowania talii kart).

To nie działa tak dobrze, jeśli chcesz (powiedzmy) 10 losowych elementów z zakresu 1..10 000 - w końcu wykonasz dużo pracy niepotrzebnie. W tym momencie prawdopodobnie lepiej jest zachować zestaw wartości, które wygenerowałeś do tej pory i po prostu generować liczby w pętli, aż następna nie będzie już obecna:

if (max < numbersNeeded)
{
    throw new IllegalArgumentException("Can't ask for more numbers than are available");
}
Random rng = new Random(); // Ideally just create one instance globally
// Note: use LinkedHashSet to maintain insertion order
Set<Integer> generated = new LinkedHashSet<Integer>();
while (generated.size() < numbersNeeded)
{
    Integer next = rng.nextInt(max) + 1;
    // As we're adding to a set, this will automatically do a containment check
    generated.add(next);
}

Uważaj jednak na wybór zestawu - użyłem go bardzo celowo, LinkedHashSetponieważ utrzymuje kolejność reklam, na czym nam zależy.

Jeszcze inną opcją jest ciągłe robienie postępów, za każdym razem zmniejszając zakres i kompensując istniejące wartości. Załóżmy na przykład, że chcesz mieć 3 wartości z zakresu 0..9. W pierwszej iteracji wygenerowałbyś dowolną liczbę z zakresu 0..9 - powiedzmy, że generujesz 4.

W drugiej iteracji wygenerowałbyś liczbę z zakresu 0..8. Jeśli wygenerowana liczba jest mniejsza niż 4, zachowasz ją tak, jak jest ... w przeciwnym razie dodasz do niej jeden. To daje zakres wyników 0..9 bez 4. Załóżmy, że w ten sposób otrzymamy 7.

W trzeciej iteracji wygenerujesz liczbę z zakresu 0..7. Jeśli wygenerowana liczba jest mniejsza niż 4, zachowaj ją tak, jak jest. Jeśli to 4 lub 5, możesz dodać jeden. Jeśli jest 6 lub 7, dodałbyś dwa. W ten sposób zakres wyników wynosi 0..9 bez 4 lub 6.

Oto jak bym to zrobił

import java.util.ArrayList;
import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int size = 20;

        ArrayList<Integer> list = new ArrayList<Integer>(size);
        for(int i = 1; i <= size; i++) {
            list.add(i);
        }

        Random rand = new Random();
        while(list.size() > 0) {
            int index = rand.nextInt(list.size());
            System.out.println("Selected: "+list.remove(index));
        }
    }
}

Jak zauważył szanowany pan Skeet:
Jeśli n to liczba losowo wybranych liczb, które chcesz wybrać, a N to całkowita przestrzeń próbna liczb dostępnych do wyboru:

1. Jeśli n << N , powinieneś po prostu zapisać wybrane liczby i sprawdzić listę, aby zobaczyć, czy wybrana liczba się na niej znajduje.
2. Jeśli n ~ = N , prawdopodobnie powinieneś użyć mojej metody, wypełniając listę zawierającą całą przestrzeń próbki, a następnie usuwając z niej liczby podczas ich wybierania.

//random numbers are 0,1,2,3 
ArrayList<Integer> numbers = new ArrayList<Integer>();   
Random randomGenerator = new Random();
while (numbers.size() < 4) {

    int random = randomGenerator .nextInt(4);
    if (!numbers.contains(random)) {
        numbers.add(random);
    }
}

Istnieje inny sposób wykonywania „losowych” uporządkowanych liczb w LFSR, spójrz na:

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

dzięki tej technice można uzyskać uporządkowaną liczbę losową według indeksu i upewnić się, że wartości nie są zduplikowane.

Ale to nie są PRAWDZIWE liczby losowe, ponieważ generowanie losowe jest deterministyczne.

Ale w zależności od przypadku możesz użyć tej techniki, zmniejszając ilość przetwarzania przy generowaniu liczb losowych podczas korzystania z tasowania.

Tutaj algorytm LFSR w javie (wziąłem go gdzieś, czego nie pamiętam):

public final class LFSR {
    private static final int M = 15;

    // hard-coded for 15-bits
    private static final int[] TAPS = {14, 15};

    private final boolean[] bits = new boolean[M + 1];

    public LFSR() {
        this((int)System.currentTimeMillis());
    }

    public LFSR(int seed) {
        for(int i = 0; i < M; i++) {
            bits[i] = (((1 << i) & seed) >>> i) == 1;
        }
    }

    /* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
    public short nextShort() {
        //printBits();

        // calculate the integer value from the registers
        short next = 0;
        for(int i = 0; i < M; i++) {
            next |= (bits[i] ? 1 : 0) << i;
        }

        // allow for zero without allowing for -2^31
        if (next < 0) next++;

        // calculate the last register from all the preceding
        bits[M] = false;
        for(int i = 0; i < TAPS.length; i++) {
            bits[M] ^= bits[M - TAPS[i]];
        }

        // shift all the registers
        for(int i = 0; i < M; i++) {
            bits[i] = bits[i + 1];
        }

        return next;
    }

    /** returns random double uniformly over [0, 1) */
    public double nextDouble() {
        return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
    }

    /** returns random boolean */
    public boolean nextBoolean() {
        return nextShort() >= 0;
    }

    public void printBits() {
        System.out.print(bits[M] ? 1 : 0);
        System.out.print(" -> ");
        for(int i = M - 1; i >= 0; i--) {
            System.out.print(bits[i] ? 1 : 0);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LFSR rng = new LFSR();
        Vector<Short> vec = new Vector<Short>();
        for(int i = 0; i <= 32766; i++) {
            short next = rng.nextShort();
            // just testing/asserting to make 
            // sure the number doesn't repeat on a given list
            if (vec.contains(next))
                throw new RuntimeException("Index repeat: " + i);
            vec.add(next);
            System.out.println(next);
        }
    }
}

Innym rozwiązaniem, które pozwala określić, ile liczb chcesz z sizea mini maxwartości zwróconych liczbach

public static int getRandomInt(int min, int max) {
    Random random = new Random();

    return random.nextInt((max - min) + 1) + min;
}

public static ArrayList<Integer> getRandomNonRepeatingIntegers(int size, int min,
        int max) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();

    while (numbers.size() < size) {
        int random = getRandomInt(min, max);

        if (!numbers.contains(random)) {
            numbers.add(random);
        }
    }

    return numbers;
}

Aby go użyć, zwracamy 7 liczb od 0 do 25.

    ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25);
    for (int i = 0; i < list.size(); i++) {
        System.out.println("" + list.get(i));
    }

Byłoby to dużo prostsze w java-8:

Stream.generate(new Random()::ints)
            .distinct()
            .limit(16) // whatever limit you might need
            .toArray(Integer[]::new);

Najbardziej efektywny, podstawowy sposób uzyskiwania niepowtarzalnych liczb losowych jest wyjaśniony za pomocą tego pseudokodu. Nie ma potrzeby posiadania zagnieżdżonych pętli ani haszowanych wyszukiwań:

// get 5 unique random numbers, possible values 0 - 19
// (assume desired number of selections < number of choices)

const int POOL_SIZE = 20;
const int VAL_COUNT = 5;

declare Array mapping[POOL_SIZE];
declare Array results[VAL_COUNT];

declare i int;
declare r int;
declare max_rand int;

// create mapping array
for (i=0; i<POOL_SIZE; i++) {
   mapping[i] = i;
}

max_rand = POOL_SIZE-1;  // start loop searching for maximum value (19)

for (i=0; i<VAL_COUNT; i++) {
    r = Random(0, max_rand); // get random number
    results[i] = mapping[r]; // grab number from map array
    mapping[r] = max_rand;  // place item past range at selected location

    max_rand = max_rand - 1;  // reduce random scope by 1
}

Załóżmy, że pierwsza iteracja wygenerowała losową liczbę 3 na początku (od 0 do 19). To dałoby wynik [0] = mapowanie [3], tj. Wartość 3. Następnie przypisalibyśmy mapowanie [3] do 19.

W kolejnej iteracji liczba losowa wynosiła 5 (od 0 do 18). To dałoby wynik [1] = mapowanie [5], tj. Wartość 5. Następnie przypisalibyśmy mapowanie [5] do 18.

Teraz załóżmy, że w następnej iteracji ponownie wybrano 3 (od 0 do 17). wynikom [2] zostanie przypisana wartość mapowania [3], ale teraz ta wartość nie wynosi 3, ale 19.

Ta sama ochrona obowiązuje dla wszystkich liczb, nawet jeśli otrzymałeś tę samą liczbę 5 razy z rzędu. Np. Jeśli generator liczb losowych poda 0 pięć razy z rzędu, wyniki będą wyglądać następująco: [0, 19, 18, 17, 16].

Nigdy nie dostaniesz dwukrotnie tej samej liczby.

Generowanie wszystkich indeksów sekwencji jest ogólnie złym pomysłem, ponieważ może zająć dużo czasu, zwłaszcza jeśli stosunek liczb do wyboru MAXjest niski (złożoność staje się dominująca O(MAX)). Sytuacja pogarsza się, gdy stosunek liczb do wyboru MAXzbliża się do jedności, ponieważ wtedy usunięcie wybranych wskaźników z ciągu wszystkich również staje się kosztowne (podchodzimy doO(MAX^2/2) ). Ale w przypadku małych liczb działa to zwykle dobrze i nie jest szczególnie podatne na błędy.

Filtrowanie wygenerowanych indeksów za pomocą kolekcji jest również złym pomysłem, ponieważ trochę czasu zajmuje wstawianie indeksów do sekwencji, a postęp nie jest gwarantowany, ponieważ ta sama liczba losowa może być losowana kilka razy (ale dla wystarczająco dużej MAXjest to mało prawdopodobne ). Może to być bardzo skomplikowane
O(k n log^2(n)/2), zignorowanie duplikatów i założenie, że kolekcja używa drzewa do wydajnego wyszukiwania (ale przy znacznym stałym koszcie kprzydzielania węzłów drzewa i prawdopodobnie konieczności ponownego równoważenia ).

Inną opcją jest generowanie wartości losowych w sposób unikalny od samego początku, gwarantując postęp. Oznacza to, że w pierwszej rundzie [0, MAX]generowany jest losowy indeks w :

items i0 i1 i2 i3 i4 i5 i6 (total 7 items)
idx 0       ^^             (index 2)

W drugiej rundzie [0, MAX - 1]generowany jest tylko (ponieważ jeden element został już wybrany):

items i0 i1    i3 i4 i5 i6 (total 6 items)
idx 1          ^^          (index 2 out of these 6, but 3 out of the original 7)

Wartości indeksów należy następnie skorygować: jeśli drugi wskaźnik przypada w drugiej połowie ciągu (po pierwszym indeksie), należy go zwiększyć, aby uwzględnić lukę. Możemy to zaimplementować jako pętlę, co pozwala nam wybrać dowolną liczbę unikalnych elementów.

Dla krótkich sekwencji jest to dość szybki O(n^2/2)algorytm:

void RandomUniqueSequence(std::vector<int> &rand_num,
    const size_t n_select_num, const size_t n_item_num)
{
    assert(n_select_num <= n_item_num);

    rand_num.clear(); // !!

    // b1: 3187.000 msec (the fastest)
    // b2: 3734.000 msec
    for(size_t i = 0; i < n_select_num; ++ i) {
        int n = n_Rand(n_item_num - i - 1);
        // get a random number

        size_t n_where = i;
        for(size_t j = 0; j < i; ++ j) {
            if(n + j < rand_num[j]) {
                n_where = j;
                break;
            }
        }
        // see where it should be inserted

        rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
        // insert it in the list, maintain a sorted sequence
    }
    // tier 1 - use comparison with offset instead of increment
}

Gdzie n_select_numjest twoja 5 i n_number_numjest twoja MAX. Do n_Rand(x)zwraca losowe liczby całkowite [0, x](włącznie). Można to zrobić nieco szybciej, wybierając wiele elementów (np. Nie 5, ale 500), używając wyszukiwania binarnego do znalezienia punktu wstawienia. Aby to zrobić, musimy upewnić się, że spełniamy wymagania.

Przeprowadzimy wyszukiwanie binarne z porównaniem, n + j < rand_num[j]które jest takie samo jak
n < rand_num[j] - j. Musimy pokazać, że rand_num[j] - jnadal jest to posortowana sekwencja dla posortowanej sekwencji rand_num[j]. Na szczęście jest to łatwe do pokazania, ponieważ najmniejsza odległość między dwoma elementami oryginału rand_numto jeden (wygenerowane liczby są unikalne, więc zawsze jest różnica co najmniej 1). Jednocześnie, jeśli odejmiemy wskaźniki jod wszystkich elementów
rand_num[j], różnice w indeksie wynoszą dokładnie 1. Tak więc w „najgorszym” przypadku otrzymujemy stałą sekwencję - ale nigdy nie malejącą. Można zatem użyć wyszukiwania binarnego, uzyskując O(n log(n))algorytm:

struct TNeedle { // in the comparison operator we need to make clear which argument is the needle and which is already in the list; we do that using the type system.
    int n;

    TNeedle(int _n)
        :n(_n)
    {}
};

class CCompareWithOffset { // custom comparison "n < rand_num[j] - j"
protected:
    std::vector<int>::iterator m_p_begin_it;

public:
    CCompareWithOffset(std::vector<int>::iterator p_begin_it)
        :m_p_begin_it(p_begin_it)
    {}

    bool operator ()(const int &r_value, TNeedle n) const
    {
        size_t n_index = &r_value - &*m_p_begin_it;
        // calculate index in the array

        return r_value < n.n + n_index; // or r_value - n_index < n.n
    }

    bool operator ()(TNeedle n, const int &r_value) const
    {
        size_t n_index = &r_value - &*m_p_begin_it;
        // calculate index in the array

        return n.n + n_index < r_value; // or n.n < r_value - n_index
    }
};

I w końcu:

void RandomUniqueSequence(std::vector<int> &rand_num,
    const size_t n_select_num, const size_t n_item_num)
{
    assert(n_select_num <= n_item_num);

    rand_num.clear(); // !!

    // b1: 3578.000 msec
    // b2: 1703.000 msec (the fastest)
    for(size_t i = 0; i < n_select_num; ++ i) {
        int n = n_Rand(n_item_num - i - 1);
        // get a random number

        std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
            TNeedle(n), CCompareWithOffset(rand_num.begin()));
        // see where it should be inserted

        rand_num.insert(p_where_it, 1, n + p_where_it - rand_num.begin());
        // insert it in the list, maintain a sorted sequence
    }
    // tier 4 - use binary search
}

Przetestowałem to na trzech testach porównawczych. Najpierw wybrano 3 liczby z 7 pozycji, a histogram wybranych pozycji zgromadził ponad 10000 serii:

4265 4229 4351 4267 4267 4364 4257

Pokazuje to, że każdy z 7 elementów został wybrany mniej więcej taką samą liczbę razy i nie ma wyraźnego błędu spowodowanego przez algorytm. Wszystkie sekwencje zostały również sprawdzone pod kątem poprawności (niepowtarzalności treści).

Drugi benchmark obejmował wybór 7 liczb spośród 5000 pozycji. W czasie kilku wersji algorytmu zgromadzono ponad 10 000 000 uruchomień. Wyniki są oznaczane w komentarzach w kodzie jako b1. Prosta wersja algorytmu jest nieco szybsza.

Trzeci benchmark obejmował wybór 700 liczb z 5000 pozycji. Ponownie skumulowano czas kilku wersji algorytmu, tym razem ponad 10 000 przebiegów. Wyniki są oznaczane w komentarzach w kodzie jako b2. Wersja algorytmu wyszukiwania binarnego jest teraz ponad dwa razy szybsza niż wersja prosta.

Druga metoda zaczyna być szybsza w przypadku wybierania więcej niż około 75 pozycji na moim komputerze (zwróć uwagę, że złożoność obu algorytmów nie zależy od liczby pozycji MAX).

Warto wspomnieć, że powyższe algorytmy generują liczby losowe w kolejności rosnącej. Ale byłoby łatwo dodać kolejną tablicę, do której liczby byłyby zapisywane w kolejności, w jakiej zostały wygenerowane, i zamiast tego zwracać ją (przy nieistotnych dodatkowych kosztach O(n)). Nie ma potrzeby tasowania wyjścia: byłoby to znacznie wolniejsze.

Zauważ, że źródła są w C ++, nie mam Javy na moim komputerze, ale koncepcja powinna być jasna.

EDYCJA :

Dla rozrywki zaimplementowałem również podejście, które generuje listę ze wszystkimi indeksami
0 .. MAX, wybiera je losowo i usuwa z listy, aby zagwarantować unikalność. Ponieważ wybrałem dość wysoką MAX(5000), wydajność jest katastrofalna:

// b1: 519515.000 msec
// b2: 20312.000 msec
std::vector<int> all_numbers(n_item_num);
std::iota(all_numbers.begin(), all_numbers.end(), 0);
// generate all the numbers

for(size_t i = 0; i < n_number_num; ++ i) {
    assert(all_numbers.size() == n_item_num - i);
    int n = n_Rand(n_item_num - i - 1);
    // get a random number

    rand_num.push_back(all_numbers[n]); // put it in the output list
    all_numbers.erase(all_numbers.begin() + n); // erase it from the input
}
// generate random numbers

Zaimplementowałem również to podejście z set(kolekcją C ++), która faktycznie zajmuje drugie miejsce w teście porównawczym b2, będąc tylko o około 50% wolniejsze niż podejście z wyszukiwaniem binarnym. Jest to zrozumiałe, ponieważ setwykorzystuje drzewo binarne, w którym koszt wstawienia jest podobny do wyszukiwania binarnego. Jedyna różnica to szansa na zdobycie zduplikowanych przedmiotów, co spowalnia postęp.

// b1: 20250.000 msec
// b2: 2296.000 msec
std::set<int> numbers;
while(numbers.size() < n_number_num)
    numbers.insert(n_Rand(n_item_num - 1)); // might have duplicates here
// generate unique random numbers

rand_num.resize(numbers.size());
std::copy(numbers.begin(), numbers.end(), rand_num.begin());
// copy the numbers from a set to a vector

Pełny kod źródłowy jest tutaj .

Możesz użyć jednej z klas implementujących interfejs Set ( API ), a następnie każdą wygenerowaną liczbę użyć Set.add (), aby ją wstawić.

Jeśli wartość zwracana jest fałszywa, wiesz, że liczba została już wygenerowana wcześniej.

Zamiast robić to wszystko, utwórz LinkedHashSetobiekt i losowe liczby do niego za pomocą Math.random()funkcji .... jeśli wystąpi zduplikowany wpis, LinkedHashSetobiekt nie doda tej liczby do swojej listy ... Ponieważ w tej klasie kolekcji nie są dozwolone zduplikowane wartości. w końcu u otrzymasz listę liczb losowych, które nie mają zduplikowanych wartości ....: D

Wydaje się, że twój problem zmniejsza się, aby wybrać losowo k elementów ze zbioru n elementów. Odpowiedź Collections.shuffle jest zatem poprawna, ale jak wskazano nieefektywna: jej O (n).

Wikipedia: Tasowanie Fishera-Yatesa ma wersję O (k), gdy tablica już istnieje. W twoim przypadku nie ma tablicy elementów, a tworzenie tablicy elementów może być bardzo kosztowne, powiedzmy, jeśli max wynosi 10000000 zamiast 20.

Algorytm tasowania polega na zainicjowaniu tablicy o rozmiarze n, w którym każdy element jest równy swojemu indeksowi, wybraniu k liczb losowych każdej liczby w zakresie, przy czym maksymalna o jeden jest mniejsza niż poprzedni zakres, a następnie zamiana elementów na końcu tablicy.

Możesz wykonać tę samą operację w czasie O (k) z haszem, chociaż przyznaję, że to rodzaj bólu. Zauważ, że jest to opłacalne tylko wtedy, gdy k jest znacznie mniejsze niż n. (tj. k ~ lg (n) lub coś podobnego), w przeciwnym razie powinieneś użyć bezpośrednio tasowania.

Użyjesz swojego hashmap jako wydajnej reprezentacji tablicy bazowej w algorytmie shuffle. Żaden element tablicy, który jest równy swojemu indeksowi, nie musi pojawiać się na mapie. Pozwala to na reprezentowanie tablicy o rozmiarze n w stałym czasie, nie ma czasu spędzonego na jej inicjalizacji.

1. Wybierz k liczb losowych: pierwsza należy do zakresu od 0 do n-1, druga od 0 do n-2, trzecia od 0 do n-3 i tak dalej, do nk.

2. Traktuj swoje liczby losowe jako zestaw zamiany. Pierwszy losowy indeks zamienia się na końcową pozycję. Drugi losowy indeks zamienia się na przedostatnią pozycję. Jednak zamiast pracować przeciwko macierzy bazowej, pracuj przeciwko swojemu hashmap. Twój hashmap przechowa każdy przedmiot, który jest na miejscu.

int getValue(i)
{
    if (map.contains(i)) 
        return map[i];
    return i;
}

void setValue(i, val)
{   
    if (i == val)
        map.remove(i);
    else
        map[i] = val;
}

int[] chooseK(int n, int k)
{
    for (int i = 0; i < k; i++)
    {
        int randomIndex = nextRandom(0, n - i); //(n - i is exclusive)
        int desiredIndex = n-i-1;

        int valAtRandom = getValue(randomIndex);
        int valAtDesired = getValue(desiredIndex);

        setValue(desiredIndex, valAtRandom);
        setValue(randomIndex, valAtDesired);
    }

    int[] output = new int[k];
    for (int i = 0; i < k; i++)
    {
        output[i] = (getValue(n-i-1));
    }

    return output;
}

Poniższy kod tworzy sekwencję liczb losowych między [1, m], która nie została wcześniej wygenerowana.

public class NewClass {

    public List<Integer> keys = new ArrayList<Integer>();

    public int rand(int m) {
        int n = (int) (Math.random() * m + 1);
        if (!keys.contains(n)) {
            keys.add(n);
            return n;
        } else {
            return rand(m);
        }
    }

    public static void main(String[] args) {
        int m = 4;
        NewClass ne = new NewClass();
        for (int i = 0; i < 4; i++) {
            System.out.println(ne.rand(m));
        }
        System.out.println("list: " + ne.keys);
    }
}

Istnieje algorytm paczki kart: tworzysz uporządkowaną tablicę liczb („pakiet kart”) iw każdej iteracji wybierasz z niej liczbę losowo (oczywiście usuwając wybraną liczbę z „partii kart”).

Oto wydajne rozwiązanie do szybkiego tworzenia losowej tablicy. Po randomizacji możesz po prostu wybrać n-ty element etablicy, inkrementować ni zwracać e. To rozwiązanie ma O (1) do uzyskania liczby losowej i O (n) do inicjalizacji, ale jako kompromis wymaga dużej ilości pamięci, jeśli n staje się wystarczająco duże.

Istnieje wydajniejsze i mniej kłopotliwe rozwiązanie dla liczb całkowitych niż Collections.shuffle.

Problem jest taki sam, jak sukcesywne wybieranie towarów tylko z niepobranych elementów w zestawie i ustawianie ich w kolejności gdzie indziej. To dokładnie tak, jak losowe rozdawanie kart lub losowanie zwycięskich kuponów na loterię z kapelusza lub kosza.

Ten algorytm działa w celu załadowania dowolnej tablicy i uzyskania losowej kolejności na końcu ładowania. Działa również w przypadku dodawania do kolekcji List (lub dowolnej innej kolekcji indeksowanej) i uzyskiwania losowej kolejności w kolekcji na końcu dodawania.

Można to zrobić za pomocą pojedynczej tablicy, utworzonej raz lub uporządkowanej numerycznie kolekcji, takiej jak Lista. W przypadku tablicy początkowy rozmiar tablicy musi być dokładny, aby zawierał wszystkie zamierzone wartości. Jeśli nie wiesz, ile wartości może wystąpić z góry, zadziała również kolekcja uporządkowana numerycznie, taka jak ArrayList lub List, w której rozmiar nie jest niezmienny. Będzie działać uniwersalnie dla tablicy o dowolnym rozmiarze do Integer.MAX_VALUE, czyli nieco ponad 2 000 000 000. Obiekty listy będą miały takie same ograniczenia indeksu. W Twojej maszynie może zabraknąć pamięci, zanim dojdziesz do tablicy o takim rozmiarze. Bardziej wydajne może być załadowanie tablicy wpisanej do typów obiektów i przekonwertowanie jej na jakąś kolekcję po załadowaniu tablicy. Jest to szczególnie ważne, jeśli kolekcja docelowa nie jest indeksowana numerycznie.

Ten algorytm, dokładnie tak, jak napisano, stworzy bardzo równą dystrybucję, w której nie ma duplikatów. Jednym z BARDZO WAŻNEGO aspektu jest to, że wstawianie następnego elementu do aktualnego rozmiaru + 1 musi być możliwe. Zatem dla drugiego elementu mogłoby być możliwe przechowywanie go w lokalizacji 0 lub lokalizacji 1 W przypadku dwudziestego elementu możliwe byłoby przechowywanie go w dowolnym miejscu, od 0 do 19. Jest tak samo możliwe, że pierwszy element pozostaje w lokalizacji 0, tak samo jak w przypadku każdego innego miejsca. Następny nowy element może przenieść się w dowolne miejsce, w tym do następnej nowej lokalizacji.

Losowość sekwencji będzie tak samo losowa, jak losowość generatora liczb losowych.

Ten algorytm może być również używany do ładowania typów odwołań do losowych lokalizacji w tablicy. Ponieważ działa to z tablicą, może również działać z kolekcjami. Oznacza to, że nie musisz tworzyć kolekcji, a następnie tasować jej lub zlecać jej porządkowanie według kolejności wstawiania obiektów. Kolekcja musi mieć tylko możliwość wstawienia elementu w dowolnym miejscu kolekcji lub dołączenia go.

// RandomSequence.java
import java.util.Random;
public class RandomSequence {

    public static void main(String[] args) {
        // create an array of the size and type for which
        // you want a random sequence
        int[] randomSequence = new int[20];
        Random randomNumbers = new Random();

        for (int i = 0; i < randomSequence.length; i++ ) {
            if (i == 0) { // seed first entry in array with item 0
                randomSequence[i] = 0; 
            } else { // for all other items...
                // choose a random pointer to the segment of the
                // array already containing items
                int pointer = randomNumbers.nextInt(i + 1);
                randomSequence[i] = randomSequence[pointer]; 
                randomSequence[pointer] = i;
                // note that if pointer & i are equal
                // the new value will just go into location i and possibly stay there
                // this is VERY IMPORTANT to ensure the sequence is really random
                // and not biased
            } // end if...else
        } // end for
        for (int number: randomSequence) {
                System.out.printf("%2d ", number);
        } // end for
    } // end main
} // end class RandomSequence

Tak naprawdę wszystko zależy od tego, do czego dokładnie potrzebujesz generowania losowego, ale oto moje podejście.

Najpierw utwórz samodzielną metodę generowania liczby losowej. Pamiętaj, aby uwzględnić ograniczenia.

public static int newRandom(int limit){
    return generatedRandom.nextInt(limit);  }

Następnie będziesz chciał stworzyć bardzo prostą strukturę decyzyjną porównującą wartości. Można to zrobić na dwa sposoby. Jeśli masz bardzo ograniczoną liczbę liczb do zweryfikowania, wystarczy prosta instrukcja IF:

public static int testDuplicates(int int1, int int2, int int3, int int4, int int5){
    boolean loopFlag = true;
    while(loopFlag == true){
        if(int1 == int2 || int1 == int3 || int1 == int4 || int1 == int5 || int1 == 0){
            int1 = newRandom(75);
            loopFlag = true;    }
        else{
            loopFlag = false;   }}
    return int1;    }

Powyższe porównuje int1 z int2 do int5, a także upewnia się, że nie ma zer w liczbach losowych.

Korzystając z tych dwóch metod, możemy wykonać następujące czynności:

    num1 = newRandom(limit1);
    num2 = newRandom(limit1);
    num3 = newRandom(limit1);
    num4 = newRandom(limit1);
    num5 = newRandom(limit1);

Śledzony przez:

        num1 = testDuplicates(num1, num2, num3, num4, num5);
        num2 = testDuplicates(num2, num1, num3, num4, num5);
        num3 = testDuplicates(num3, num1, num2, num4, num5);
        num4 = testDuplicates(num4, num1, num2, num3, num5);
        num5 = testDuplicates(num5, num1, num2, num3, num5);

Jeśli masz dłuższą listę do zweryfikowania, bardziej złożona metoda zapewni lepsze wyniki zarówno w zakresie przejrzystości kodu, jak i przetwarzania zasobów.

Mam nadzieję że to pomoże. Ta strona pomogła mi tak bardzo, że czułem się zobowiązany przynajmniej SPRÓBOWAĆ pomóc.

Utworzyłem fragment, który nie generuje zduplikowanej losowej liczby całkowitej. Zaletą tego fragmentu jest to, że możesz przypisać do niego listę tablicy i wygenerować również losowy element.

Brak duplikacji klasy generatora losowego

Najłatwiejszym sposobem jest użycie nano DateTime jako długiego formatu. System.nanoTime ();