Vraag Maken van willekeurige getallen zonder duplicaten


In dit geval is de MAX slechts 5, dus ik kon de duplicaten één voor één controleren, maar hoe kon ik dit op een eenvoudiger manier doen? Wat als bijvoorbeeld de MAX een waarde van 20 heeft? Bedankt.

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

}

72
2017-10-28 05:23


oorsprong


antwoorden:


De eenvoudigste manier zou zijn om een ​​lijst met mogelijke nummers (1..20 of wat dan ook) te maken en deze vervolgens te shufflen Collections.shuffle. Neem dan gewoon veel elementen die u wilt. Dit is geweldig als uw bereik gelijk is aan het aantal elementen dat u op het einde nodig heeft (bijvoorbeeld voor het schudden van een spel kaarten).

Dat werkt niet zo goed als je (wil zeggen) 10 willekeurige elementen in het bereik van 1..10.000 wilt - je zou onnodig veel werk gaan doen. Op dat moment is het waarschijnlijk beter om een ​​reeks waarden te bewaren die je tot nu toe hebt gegenereerd, en gewoon nummers in een lus te genereren totdat de volgende nog niet aanwezig is:

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

Wees echter voorzichtig met de ingestelde keuze - ik heb het heel bewust gebruikt LinkedHashSet omdat het invoegvolgorde onderhoudt, waar we hier om geven.

Nog een andere optie is om altijd vooruitgang boeken door het bereik elke keer te verkleinen en bestaande waarden te compenseren. Stel dat u bijvoorbeeld 3 waarden in het bereik 0,9 wilde hebben. Bij de eerste iteratie zou u elk willekeurig nummer genereren in het bereik 0..9 - laten we zeggen dat u een 4 genereert.

Bij de tweede iteratie zou je dan een getal genereren in het bereik 0..8. Als het gegenereerde aantal kleiner is dan 4, zou je het behouden zoals het is ... anders voeg je er een toe. Dat levert een resultaatbereik op van 0..9 zonder 4. Stel dat we op die manier 7 krijgen.

Op de derde iteratie zou je een getal genereren in het bereik 0..7. Als het gegenereerde aantal kleiner is dan 4, zou je het behouden zoals het is. Als het 4 of 5 is, zou je er een toevoegen. Als het 6 of 7 is, voeg je er twee toe. Op die manier is het resultaatbereik 0..9 zonder 4 of 6.


133
2017-10-28 05:25



Dit is hoe ik het zou doen

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

Zoals de geachte heer Skeet heeft opgemerkt:
Als n is het aantal willekeurig gekozen nummers dat u wilt kiezen en N is de totale steekproefruimte van beschikbare nummers voor selectie:

  1. Als n << N, u moet gewoon de nummers opslaan die u hebt gekozen en een lijst controleren om te zien of het geselecteerde nummer erin voorkomt.
  2. Als n ~ = N, u zou waarschijnlijk mijn methode moeten gebruiken, door een lijst te vullen die de volledige steekproefruimte bevat en dan aantallen van het te verwijderen aangezien u hen selecteert.

18
2017-10-28 05:30



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

10
2018-04-13 07:28



De meest efficiënte, basale manier om niet-herhalende willekeurige getallen te hebben, wordt verklaard door deze pseudo-code. Het is niet nodig om geneste lussen of hash-lookups te hebben:

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

Stel dat de eerste iteratie willekeurig nummer 3 heeft gegenereerd om te starten (van 0 - 19). Dit zou resultaten [0] = toewijzing [3] maken, d.w.z. de waarde 3. We zouden dan toewijzing [3] toewijzen aan 19.

In de volgende iteratie was het willekeurige getal 5 (van 0 - 18). Dit zou resultaten [1] = afbeelding [5] maken, d.w.z. de waarde 5. We zouden dan toewijzing [5] aan 18 toewijzen.

Stel nu dat de volgende iteratie opnieuw 3 kiest (van 0 - 17). resultaten [2] krijgen de waarde toegewezen van mapping [3], maar nu is deze waarde geen 3, maar 19.

Deze bescherming blijft gelden voor alle nummers, zelfs als u vijf keer achter elkaar hetzelfde nummer hebt. Bijvoorbeeld, als de generator voor willekeurige getallen u vijfmaal achter elkaar 0 gaf, zouden de resultaten zijn: [0, 19, 18, 17, 16].

Je zou nooit hetzelfde nummer twee keer krijgen.


3
2017-10-01 20:28



Het genereren van alle indices van een reeks is over het algemeen een slecht idee, omdat het veel tijd kost, vooral als de verhouding van de te kiezen nummers tot MAX is laag (de complexiteit wordt gedomineerd door O(MAX)). Dit wordt erger als de verhouding van de te kiezen nummers tot MAX benadert een, omdat het verwijderen van de gekozen indices uit de reeks van allemaal ook duur wordt (we naderen O(MAX^2/2)). Maar voor kleine aantallen werkt dit over het algemeen goed en is het niet bijzonder foutgevoelig.

Het filteren van de gegenereerde indices met behulp van een verzameling is ook een slecht idee, omdat er enige tijd wordt besteed aan het invoegen van de indices in de reeks, en de voortgang wordt niet gegarandeerd omdat hetzelfde willekeurige nummer meerdere keren kan worden getrokken (maar voor voldoende groot). MAX het is onwaarschijnlijk). Dit kan dicht bij de complexiteit liggen
O(k n log^2(n)/2), de duplicaten negerend en ervan uitgaande dat de verzameling een boom gebruikt voor een efficiënte opzoeking (maar met een aanzienlijke constante kosten k van het toewijzen van de boomknooppunten en mogelijk aan herbalanceren).

Een andere optie is om de willekeurige waarden vanaf het begin uniek te genereren, zodat wordt gegarandeerd dat er vooruitgang wordt geboekt. Dat betekent in de eerste ronde een willekeurige index in [0, MAX] is gegenereerd:

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

Alleen in de tweede ronde [0, MAX - 1] wordt gegenereerd (omdat één item al was geselecteerd):

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)

De waarden van de indices moeten vervolgens worden aangepast: als de tweede index in de tweede helft van de reeks valt (na de eerste index), moet deze worden opgehoogd om rekening te houden met de kloof. We kunnen dit als een lus implementeren, waardoor we een willekeurig aantal unieke items kunnen selecteren.

Voor korte reeksen is dit vrij snel O(n^2/2) algoritme:

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
}

Waar n_select_num is jouw 5 en n_number_num is jouw MAX. De n_Rand(x) geeft willekeurige getallen terug in [0, x] (Inclusief). Dit kan een beetje sneller worden gemaakt als u veel items selecteert (bijvoorbeeld niet 5 maar 500) door binaire zoekacties te gebruiken om het invoegpunt te vinden. Om dat te doen, moeten we ervoor zorgen dat we aan de vereisten voldoen.

We zullen binair zoeken met de vergelijking n + j < rand_num[j] welke hetzelfde is als
n < rand_num[j] - j. We moeten dat laten zien rand_num[j] - j is nog steeds een gesorteerde reeks voor een gesorteerde reeks rand_num[j]. Dit is gelukkig gemakkelijk te zien, als de laagste afstand tussen twee elementen van het origineel rand_num is één (de gegenereerde getallen zijn uniek, dus er is altijd een verschil van ten minste 1). Tegelijkertijd, als we de indexen aftrekken j van alle elementen
rand_num[j], de indexverschillen zijn exact 1. Dus in het "slechtste" geval krijgen we een constante volgorde - maar nooit minder. De binaire zoekactie kan daarom worden gebruikt, waarbij wordt meegegeven O(n log(n)) algoritme:

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

En tenslotte:

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
}

Ik heb dit getest op drie benchmarks. Eerst werden 3 nummers gekozen uit 7 items en een histogram van de gekozen items werd verzameld over 10.000 runs:

4265 4229 4351 4267 4267 4364 4257

Dit toont aan dat elk van de 7 items ongeveer hetzelfde aantal keer is gekozen, en er is geen schijnbare vertekening veroorzaakt door het algoritme. Alle sequenties werden ook gecontroleerd op juistheid (uniciteit van de inhoud).

De tweede benchmark omvatte het kiezen van 7 nummers uit 5000 items. De tijd van verschillende versies van het algoritme was verzameld over 10.000.000 runs. De resultaten worden aangegeven in opmerkingen in de code als b1. De eenvoudige versie van het algoritme is iets sneller.

De derde benchmark betrof het kiezen van 700 nummers uit 5000 items. De tijd van verschillende versies van het algoritme werd opnieuw verzameld, ditmaal meer dan 10.000 runs. De resultaten worden aangegeven in opmerkingen in de code als b2. De binaire zoekversie van het algoritme is nu meer dan twee keer sneller dan de eenvoudige.

De tweede methode begint sneller te zijn bij het kiezen van meer dan cca 75 items op mijn machine (merk op dat de complexiteit van beide algoritmen niet afhankelijk is van het aantal items, MAX).

Het is vermeldenswaard dat de bovenstaande algoritmen de willekeurige getallen in stijgende volgorde genereren. Maar het zou eenvoudig zijn om een ​​andere array toe te voegen waarnaar de nummers zouden worden opgeslagen in de volgorde waarin ze waren gegenereerd, en dat in plaats daarvan terug te geven (tegen te verwaarlozen extra kosten O(n)). Het is niet nodig om de uitvoer te schudden: dat zou veel langzamer zijn.

Merk op dat de bronnen zich in C ++ bevinden, ik heb geen Java op mijn machine, maar het concept moet duidelijk zijn.

BEWERK:

Ter vermaak heb ik ook de aanpak geïmplementeerd die een lijst genereert met alle indices
0 .. MAX, kiest ze willekeurig en verwijdert ze uit de lijst om uniciteit te garanderen. Omdat ik vrij hoog heb gekozen MAX (5000), de uitvoering is catastrofaal:

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

Ik heb de aanpak ook geïmplementeerd met een set (een C ++ -collectie), die eigenlijk als tweede op de benchmark komt b2, slechts ongeveer 50% langzamer dan de benadering met de binaire zoekopdracht. Dat is begrijpelijk, net als de set gebruikt een binaire structuur, waarbij de invoegkosten vergelijkbaar zijn met binair zoeken. Het enige verschil is de kans op dubbele items, waardoor de voortgang wordt vertraagd.

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

Volledige broncode is hier.


3
2017-12-16 17:49



Een andere benadering waarmee u kunt opgeven met hoeveel nummers u wilt size en de min en max waarden van de geretourneerde nummers

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

Om het te gebruiken, retourneert 7 cijfers tussen 0 en 25.

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

3
2018-06-15 23:32



U zou een van de klassen kunnen gebruiken die de Set-interface implementeren (API) en vervolgens elk nummer dat u genereert, gebruikt u Set.add () om het in te voegen.

Als de geretourneerde waarde onwaar is, weet u dat het nummer al eerder is gegenereerd.


2
2017-10-28 05:39



In plaats van dit alles te doen creëer een LinkedHashSet object en willekeurige nummers ernaar door Math.random() functie .... als er een dubbele invoer plaatsvindt, de LinkedHashSet object voegt dat nummer niet toe aan zijn lijst ... Omdat in deze collectieklasse geen dubbele waarden zijn toegestaan ​​.. krijgt u uiteindelijk een lijst met willekeurige getallen zonder gedupliceerde waarden ....: D


2
2018-01-14 15:52



Er is een andere manier om "willekeurige" geordende nummers met LFSR te doen, kijk eens naar:

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

met deze techniek kunt u het geordende willekeurige getal per index bereiken en ervoor zorgen dat de waarden niet worden gedupliceerd.

Maar dit zijn geen WARE willekeurige getallen omdat de willekeurige generatie deterministisch is.

Maar afhankelijk van je zaak u kunt deze techniek gebruiken om de hoeveelheid verwerking bij het genereren van willekeurige getallen te verminderen bij gebruik van shuffelen.

Hier een LFSR-algoritme in java, (ik heb het ergens meegenomen, ik herinner het niet meer):

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

2
2017-09-24 14:54



Je probleem lijkt te verminderen om willekeurige k-elementen te kiezen uit een verzameling van n elementen. Het antwoord Collections.shuffle is dus correct, maar zoals aangegeven inefficiënt: de O (n).

Wikipedia: Fisher-Yates shuffle heeft een O (k) -versie wanneer de array al bestaat. In uw geval is er geen reeks elementen en het maken van de reeks elementen kan erg duur zijn, bijvoorbeeld als max 10.000000 zijn in plaats van 20.

Het shuffle-algoritme omvat het initialiseren van een array van grootte n waarbij elk element gelijk is aan zijn index, waarbij k willekeurige getallen elk nummer in een bereik met de max één minder dan het vorige bereik worden opgepakt en vervolgens elementen naar het einde van de array worden geruild.

Je kunt dezelfde bewerking in O (k) -tijd doen met een hashkaart, hoewel ik toegeef dat het een soort pijn is. Merk op dat dit alleen de moeite waard is als k veel minder is dan n. (dwz k ~ lg (n) of zo), anders zou u de shuffle direct moeten gebruiken.

U gebruikt uw hash-map als een efficiënte weergave van de achtergrondarray in het shuffle-algoritme. Elk element van de array dat gelijk is aan de index hoeft niet op de kaart te verschijnen. Hiermee kunt u een array van grootte n in constante tijd weergeven, er is geen tijd om het te initialiseren.

  1. Kies k willekeurige getallen: de eerste is in het bereik van 0 tot n-1, de tweede van 0 tot n-2, de derde van 0 tot n-3 enzovoort, tot en met n-k.

  2. Behandel je willekeurige nummers als een set swaps. De eerste willekeurige index wisselt naar de laatste positie. De tweede willekeurige index wisselt naar de een na de ander positie. In plaats van tegen een achtergrondarray te werken, werkt u echter tegen uw hashmap. Uw hashmap slaat elk item op dat niet op zijn plaats zit.

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

2
2017-12-27 19:50