Membuat nomor acak tanpa duplikat

Dalam hal ini, MAX hanya 5, jadi saya dapat memeriksa duplikatnya satu per satu, tetapi bagaimana saya bisa melakukan ini dengan cara yang lebih sederhana? Misalnya, bagaimana jika MAX memiliki nilai 20? Terima kasih.

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

}

Cara termudah adalah dengan membuat daftar kemungkinan nomor (1..20 atau apapun) dan kemudian mengocoknya dengan Collections.shuffle. Kemudian ambil saja banyak elemen yang Anda inginkan. Ini bagus jika jangkauan Anda sama dengan jumlah elemen yang Anda butuhkan pada akhirnya (misalnya untuk mengocok setumpuk kartu).

Itu tidak bekerja dengan baik jika Anda menginginkan (katakanlah) 10 elemen acak dalam kisaran 1..10.000 - Anda akan melakukan banyak pekerjaan yang tidak perlu. Pada titik itu, mungkin lebih baik menyimpan sekumpulan nilai yang telah Anda hasilkan sejauh ini, dan terus menghasilkan angka dalam satu putaran sampai nilai berikutnya belum ada:

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

Berhati-hatilah dengan pilihan yang ditetapkan - Saya sengaja menggunakannya LinkedHashSetkarena mempertahankan urutan penyisipan, yang kami pedulikan di sini.

Pilihan lainnya adalah selalu membuat kemajuan, dengan mengurangi jarak setiap saat dan mengimbangi nilai yang ada. Jadi misalnya, Anda menginginkan 3 nilai dalam rentang 0..9. Pada iterasi pertama, Anda akan menghasilkan angka apa pun dalam rentang 0..9 - misalkan Anda menghasilkan 4.

Pada iterasi kedua Anda kemudian akan menghasilkan angka dalam kisaran 0..8. Jika nomor yang dihasilkan kurang dari 4, Anda akan tetap seperti apa adanya ... jika tidak, tambahkan satu. Itu memberi Anda rentang hasil 0..9 tanpa 4. Misalkan kita mendapatkan 7 dengan cara itu.

Pada iterasi ketiga Anda akan menghasilkan angka dalam kisaran 0..7. Jika angka yang dihasilkan kurang dari 4, Anda akan membiarkannya apa adanya. Jika 4 atau 5, Anda akan menambahkan satu. Jika 6 atau 7, Anda akan menambahkan dua. Dengan demikian, rentang hasilnya adalah 0..9 tanpa 4 atau 6.

Begini cara saya melakukannya

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

Seperti yang ditunjukkan oleh Tuan Skeet yang terhormat:
Jika n adalah jumlah nomor yang dipilih secara acak yang ingin Anda pilih dan N adalah total ruang sampel dari nomor yang tersedia untuk dipilih:

1. Jika n << N , Anda harus menyimpan nomor yang telah Anda pilih dan memeriksa daftar untuk melihat apakah nomor yang dipilih ada di dalamnya.
2. Jika n ~ = N , Anda mungkin harus menggunakan metode saya, dengan mengisi daftar yang berisi seluruh ruang sampel dan kemudian menghapus nomor darinya saat Anda memilihnya.

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

Ada cara lain untuk melakukan nomor urut "acak" dengan LFSR, lihat:

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

dengan teknik ini Anda dapat mencapai nomor acak yang diurutkan berdasarkan indeks dan memastikan nilainya tidak terduplikasi.

Tapi ini bukan bilangan acak BENAR karena pembangkitan acak bersifat deterministik.

Tapi tergantung kasus Anda Anda, Anda dapat menggunakan teknik ini untuk mengurangi jumlah pemrosesan pada pembuatan nomor acak saat menggunakan pengacakan.

Berikut algoritma LFSR di java, (Saya membawanya ke suatu tempat yang tidak saya ingat):

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

Pendekatan lain yang memungkinkan Anda untuk menentukan berapa banyak angka yang Anda inginkan sizedan nilai mindan maxdari angka yang dikembalikan

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

Untuk menggunakannya mengembalikan 7 angka antara 0 dan 25.

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

Ini akan jauh lebih sederhana dalam java-8:

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

Cara paling efisien dan dasar untuk mendapatkan nomor acak yang tidak berulang dijelaskan oleh kode-semu ini. Tidak perlu memiliki loop bersarang atau pencarian berciri:

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

Misalkan iterasi pertama menghasilkan angka acak 3 untuk memulai (dari 0 - 19). Ini akan membuat hasil [0] = pemetaan [3], yaitu nilai 3. Kami kemudian menetapkan pemetaan [3] menjadi 19.

Pada iterasi selanjutnya didapatkan angka random 5 (dari 0 - 18). Ini akan membuat hasil [1] = pemetaan [5], yaitu nilai 5. Kami kemudian menetapkan pemetaan [5] menjadi 18.

Sekarang misalkan iterasi berikutnya memilih 3 lagi (dari 0 - 17). hasil [2] akan diberi nilai pemetaan [3], tapi sekarang, nilai ini bukan 3, tetapi 19.

Perlindungan yang sama ini berlaku untuk semua nomor, bahkan jika Anda mendapatkan nomor yang sama sebanyak 5 kali berturut-turut. Misalnya, jika generator bilangan acak memberi Anda 0 lima kali berturut-turut, hasilnya adalah: [0, 19, 18, 17, 16].

Anda tidak akan pernah mendapatkan nomor yang sama dua kali.

Menghasilkan semua indeks dari suatu urutan umumnya merupakan ide yang buruk, karena mungkin membutuhkan banyak waktu, terutama jika rasio angka yang akan dipilih MAXrendah (kompleksitas menjadi didominasi oleh O(MAX)). Ini menjadi lebih buruk jika rasio angka yang akan dipilih MAXmendekati satu, karena kemudian menghapus indeks yang dipilih dari urutan semua juga menjadi mahal (kami mendekatiO(MAX^2/2) ). Tetapi untuk jumlah kecil, ini umumnya berfungsi dengan baik dan tidak terlalu rawan kesalahan.

Memfilter indeks yang dihasilkan dengan menggunakan koleksi juga merupakan ide yang buruk, karena beberapa waktu dihabiskan untuk memasukkan indeks ke dalam urutan, dan kemajuan tidak dijamin karena nomor acak yang sama dapat ditarik beberapa kali (tetapi untuk yang cukup besar MAXkemungkinannya kecil. ). Ini bisa mendekati kompleksitas
O(k n log^2(n)/2), mengabaikan duplikat dan mengasumsikan koleksi menggunakan pohon untuk pencarian yang efisien (tetapi dengan biaya konstan yang signifikan kuntuk mengalokasikan simpul pohon dan mungkin harus menyeimbangkan ulang ).

Pilihan lainnya adalah menghasilkan nilai acak secara unik sejak awal, menjamin kemajuan sedang dibuat. Itu berarti di babak pertama, indeks acak dalam [0, MAX]dihasilkan:

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

Di babak kedua, hanya [0, MAX - 1]dibuat (karena satu item telah dipilih):

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)

Nilai-nilai indeks kemudian perlu disesuaikan: jika indeks kedua jatuh di paruh kedua urutan (setelah indeks pertama), itu perlu ditambahkan untuk memperhitungkan kesenjangan. Kita bisa mengimplementasikan ini sebagai loop, memungkinkan kita memilih sembarang jumlah item unik.

Untuk urutan pendek, ini adalah O(n^2/2)algoritme yang cukup cepat :

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
}

Dimana n_select_num5 Anda dan milik n_number_numAnda MAX. The n_Rand(x)mengembalikan bilangan bulat acak di[0, x] (inklusif). Ini dapat dibuat sedikit lebih cepat jika memilih banyak item (misalnya bukan 5 tetapi 500) dengan menggunakan pencarian biner untuk menemukan titik penyisipan. Untuk melakukan itu, kami perlu memastikan bahwa kami memenuhi persyaratan.

Kami akan melakukan pencarian biner dengan perbandingan n + j < rand_num[j]yang sama
n < rand_num[j] - j. Kita perlu menunjukkan bahwa rand_num[j] - jmasih merupakan urutan terurut untuk urutan terurut rand_num[j]. Untungnya, ini mudah ditampilkan, karena jarak terendah antara dua elemen aslinya rand_numadalah satu (angka yang dihasilkan unik, jadi selalu ada selisih minimal 1). Pada saat yang sama, jika kita mengurangi indeks jdari semua elemen
rand_num[j], perbedaan indeksnya persis 1. Jadi dalam kasus "terburuk", kita mendapatkan urutan konstan - tetapi tidak pernah menurun. Oleh karena itu, pencarian biner dapat digunakan, menghasilkan O(n log(n))algoritma:

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

Dan akhirnya:

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
}

Saya telah menguji ini pada tiga tolok ukur. Pertama, 3 nomor dipilih dari 7 item, dan histogram item yang dipilih dikumpulkan lebih dari 10.000 proses:

4265 4229 4351 4267 4267 4364 4257

Ini menunjukkan bahwa masing-masing dari 7 item dipilih kira-kira dalam jumlah yang sama, dan tidak ada bias yang disebabkan oleh algoritma. Semua urutan juga diperiksa kebenarannya (keunikan isinya).

Tolok ukur kedua melibatkan pemilihan 7 angka dari 5000 item. Waktu dari beberapa versi algoritme diakumulasikan lebih dari 10.000.000 berjalan. Hasilnya dilambangkan dalam komentar di kode sebagaib1 . Versi algoritme yang sederhana sedikit lebih cepat.

Tolok ukur ketiga melibatkan pemilihan 700 nomor dari 5000 item. Waktu dari beberapa versi algoritme dikumpulkan kembali, kali ini lebih dari 10.000 berjalan. Hasilnya dilambangkan dalam komentar di kode sebagaib2 . Versi penelusuran biner dari algoritme sekarang lebih dari dua kali lebih cepat daripada versi sederhana.

Metode kedua mulai lebih cepat untuk memilih lebih dari 75 item cca di mesin saya (perhatikan bahwa kompleksitas algoritme mana pun tidak bergantung pada jumlah item, MAX).

Perlu disebutkan bahwa algoritme di atas menghasilkan angka acak dalam urutan menaik. Tetapi akan mudah untuk menambahkan larik lain yang nomornya akan disimpan sesuai urutan pembuatannya, dan mengembalikannya sebagai gantinya (dengan biaya tambahan yang dapat diabaikan O(n)). Tidak perlu mengacak keluaran: itu akan jauh lebih lambat.

Perhatikan bahwa sumbernya ada dalam C ++, saya tidak memiliki Java di komputer saya, tetapi konsepnya harus jelas.

EDIT :

Untuk hiburan, saya juga telah menerapkan pendekatan yang menghasilkan daftar dengan semua indeks
0 .. MAX, memilihnya secara acak dan menghapusnya dari daftar untuk menjamin keunikan. Karena saya telah memilih cukup tinggi MAX(5000), kinerjanya sangat dahsyat:

// 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

Saya juga telah menerapkan pendekatan dengan set(koleksi C ++), yang sebenarnya berada di urutan kedua pada benchmark b2, hanya sekitar 50% lebih lambat daripada pendekatan dengan pencarian biner. Hal ini dapat dimaklumi, karena setmenggunakan pohon biner, di mana biaya penyisipannya mirip dengan pencarian biner. Satu-satunya perbedaan adalah peluang mendapatkan item duplikat, yang memperlambat kemajuan.

// 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

Kode sumber lengkap ada di sini .

Anda bisa menggunakan salah satu kelas yang mengimplementasikan antarmuka Set ( API ), lalu setiap angka yang Anda buat, gunakan Set.add () untuk menyisipkannya.

Jika nilai yang dikembalikan salah, Anda tahu nomor tersebut telah dihasilkan sebelumnya.

Alih-alih melakukan semua ini, buat LinkedHashSetobjek dan angka acak berdasarkan Math.random()fungsi .... jika ada entri duplikat, LinkedHashSetobjek tidak akan menambahkan angka itu ke Daftarnya ... Karena di Kelas Koleksi ini tidak ada nilai duplikat yang diizinkan .. pada akhirnya Anda mendapatkan daftar nomor acak yang tidak memiliki nilai duplikat ....: D

Masalah Anda tampaknya berkurang untuk memilih k elemen secara acak dari kumpulan n elemen. Dengan demikian, jawaban Collections.shuffle benar, tetapi seperti yang ditunjukkan tidak efisien: O (n) nya.

Wikipedia: Fisher – Yates shuffle memiliki versi O (k) saat array sudah ada. Dalam kasus Anda, tidak ada larik elemen dan membuat larik elemen bisa sangat mahal, katakanlah jika maks adalah 10.000.000, bukan 20.

Algoritme acak melibatkan inisialisasi larik dengan ukuran n di mana setiap elemen sama dengan indeksnya, memilih k bilangan acak setiap nomor dalam rentang dengan maksimal satu kurang dari rentang sebelumnya, lalu menukar elemen ke akhir larik.

Anda dapat melakukan operasi yang sama dalam waktu O (k) dengan hashmap meskipun saya mengakuinya agak merepotkan. Perhatikan bahwa ini hanya berguna jika k jauh lebih kecil dari n. (mis. k ~ lg (n) atau lebih), jika tidak, Anda harus menggunakan pengacakan secara langsung.

Anda akan menggunakan hashmap Anda sebagai representasi efisien dari larik dukungan dalam algoritma shuffle. Setiap elemen dari array yang sama dengan indeksnya tidak perlu muncul di peta. Ini memungkinkan Anda untuk mewakili larik berukuran n dalam waktu yang konstan, tidak ada waktu yang dihabiskan untuk memulainya.

1. Pilih k bilangan acak: yang pertama ada di kisaran 0 sampai n-1, yang kedua 0 sampai n-2, yang ketiga 0 sampai n-3 dan seterusnya, sampai nk.

2. Perlakukan nomor acak Anda sebagai satu set swap. Indeks acak pertama bertukar ke posisi akhir. Indeks acak kedua bertukar ke posisi kedua hingga terakhir. Namun, alih-alih menggunakan backing array, kerjakan dengan hashmap Anda. Hashmap Anda akan menyimpan setiap item yang keluar dari posisinya.

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

Kode berikut membuat nomor acak urutan antara [1, m] yang tidak dibuat sebelumnya.

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

Cara paling mudah adalah menggunakan nano DateTime sebagai format panjang. System.nanoTime ();

Ada algoritme kumpulan kartu: Anda membuat susunan nomor yang diurutkan ("kumpulan kartu") dan di setiap iterasi Anda memilih nomor secara acak dari situ (tentu saja menghapus nomor yang dipilih dari "kumpulan kartu").

Berikut adalah solusi efisien untuk pembuatan cepat larik acak. Setelah pengacakan, Anda cukup memilih nelemen -th edari array, increment ndan return e. Solusi ini memiliki O (1) untuk mendapatkan bilangan acak dan O (n) untuk inisialisasi, tetapi sebagai tradeoff membutuhkan jumlah memori yang baik jika n menjadi cukup besar.

Ada solusi yang lebih efisien dan tidak terlalu rumit untuk bilangan bulat daripada Collections.shuffle.

Masalahnya sama dengan memilih item secara berurutan hanya dari item yang tidak diambil dalam satu set dan mengaturnya di tempat lain. Ini persis seperti pembagian kartu secara acak atau menggambar tiket undian yang menang dari topi atau tempat sampah.

Algoritme ini berfungsi untuk memuat larik apa pun dan mencapai urutan acak di akhir pemuatan. Ini juga berfungsi untuk menambahkan ke dalam koleksi Daftar (atau koleksi terindeks lainnya) dan mencapai urutan acak dalam koleksi di akhir penambahan.

Ini dapat dilakukan dengan satu larik, dibuat sekali, atau koleksi yang diurutkan secara numerik, seperti Daftar, di tempat. Untuk larik, ukuran larik awal harus berukuran tepat untuk memuat semua nilai yang diinginkan. Jika Anda tidak mengetahui berapa banyak nilai yang mungkin terjadi sebelumnya, menggunakan koleksi yang diurutkan secara numerik, seperti ArrayList atau List, yang ukurannya tidak dapat diubah, juga akan berfungsi. Ini akan bekerja secara universal untuk larik dengan berbagai ukuran hingga Integer.MAX_VALUE yang jumlahnya lebih dari 2.000.000.000. Objek daftar akan memiliki batas indeks yang sama. Mesin Anda mungkin kehabisan memori sebelum Anda mendapatkan larik sebesar itu. Mungkin lebih efisien untuk memuat larik yang diketik ke tipe objek dan mengubahnya menjadi beberapa koleksi, setelah memuat larik. Hal ini terutama berlaku jika kumpulan target tidak diindeks secara numerik.

Algoritma ini, persis seperti yang tertulis, akan membuat distribusi yang sangat merata di mana tidak ada duplikat. Salah satu aspek yang SANGAT PENTING adalah penyisipan item berikutnya harus dimungkinkan hingga ukuran saat ini + 1. Jadi, untuk item kedua, dimungkinkan untuk menyimpannya di lokasi 0 atau lokasi 1 Untuk item ke-20, item tersebut dapat disimpan di lokasi mana pun, 0 hingga 19. Item pertama dapat disimpan di lokasi 0 sama seperti item tersebut berakhir di lokasi lain. Item baru berikutnya dapat dibawa ke mana saja, termasuk lokasi baru berikutnya.

Keacakan urutan akan seacak seperti keacakan generator nomor acak.

Algoritme ini juga dapat digunakan untuk memuat jenis referensi ke lokasi acak dalam larik. Karena ini berfungsi dengan array, ini juga dapat bekerja dengan koleksi. Itu berarti Anda tidak perlu membuat koleksi lalu mengocoknya atau mengaturnya sesuai urutan objek yang akan disisipkan. Koleksi hanya perlu memiliki kemampuan untuk memasukkan item di mana saja dalam koleksi atau menambahkannya.

// 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

Itu benar-benar semua tergantung pada APA yang Anda butuhkan untuk generasi acak, tapi inilah pendapat saya.

Pertama, buat metode mandiri untuk menghasilkan nomor acak. Pastikan untuk memberikan batasan.

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

Selanjutnya, Anda akan ingin membuat struktur keputusan yang sangat sederhana yang membandingkan nilai. Ini dapat dilakukan dengan salah satu dari dua cara. Jika Anda memiliki jumlah angka yang sangat terbatas untuk diverifikasi, pernyataan IF sederhana sudah cukup:

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

Di atas membandingkan int1 ke int2 hingga int5, serta memastikan bahwa tidak ada angka nol dalam randoms.

Dengan dua metode ini, kita dapat melakukan hal berikut:

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

Diikuti oleh:

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

Jika Anda memiliki daftar yang lebih panjang untuk diverifikasi, maka metode yang lebih kompleks akan memberikan hasil yang lebih baik baik dalam kejelasan kode maupun dalam sumber daya pemrosesan.

Semoga ini membantu. Situs ini telah banyak membantu saya, saya merasa berkewajiban untuk setidaknya MENCOBA untuk membantu juga.

Saya membuat potongan yang tidak menghasilkan duplikat bilangan bulat acak. keuntungan dari cuplikan ini adalah Anda dapat menetapkan daftar larik ke dalamnya dan juga menghasilkan item acak.

Tidak ada duplikasi kelas generator acak