Zufallszahlen ohne Duplikate erstellen

In diesem Fall ist der MAX nur 5, sodass ich die Duplikate einzeln überprüfen kann. Wie kann ich dies jedoch einfacher tun? Was ist zum Beispiel, wenn der MAX einen Wert von 20 hat? Vielen Dank.

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

}

Am einfachsten wäre es, eine Liste der möglichen Zahlen (1..20 oder was auch immer) zu erstellen und diese dann zu mischen Collections.shuffle. Dann nehmen Sie einfach so viele Elemente, wie Sie möchten. Dies ist großartig, wenn Ihre Reichweite der Anzahl der Elemente entspricht, die Sie am Ende benötigen (z. B. zum Mischen eines Kartenspiels).

Das funktioniert nicht so gut, wenn Sie 10 zufällige Elemente im Bereich von 1 bis 10.000 möchten (sagen wir) - Sie würden am Ende unnötig viel Arbeit erledigen. An diesem Punkt ist es wahrscheinlich besser, eine Reihe von Werten, die Sie bisher generiert haben, beizubehalten und Zahlen in einer Schleife zu generieren, bis die nächste nicht mehr vorhanden ist:

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

Seien Sie jedoch vorsichtig mit der Auswahl des Sets - ich habe es sehr bewusst verwendet, LinkedHashSetda es die Einfügereihenfolge beibehält, die uns hier wichtig ist.

Eine weitere Möglichkeit besteht darin, immer Fortschritte zu erzielen, indem der Bereich jedes Mal verringert und vorhandene Werte ausgeglichen werden. Angenommen, Sie möchten 3 Werte im Bereich 0..9. Bei der ersten Iteration würden Sie eine beliebige Zahl im Bereich 0..9 generieren - nehmen wir an, Sie generieren eine 4.

Bei der zweiten Iteration würden Sie dann eine Zahl im Bereich 0..8 generieren. Wenn die generierte Zahl kleiner als 4 ist, behalten Sie sie unverändert bei. Andernfalls fügen Sie eine hinzu. Das ergibt einen Ergebnisbereich von 0..9 ohne 4. Angenommen, wir erhalten auf diese Weise 7.

Bei der dritten Iteration würden Sie eine Zahl im Bereich 0..7 generieren. Wenn die generierte Zahl kleiner als 4 ist, behalten Sie sie unverändert bei. Wenn es 4 oder 5 ist, würden Sie eine hinzufügen. Wenn es 6 oder 7 ist, würden Sie zwei hinzufügen. Auf diese Weise beträgt der Ergebnisbereich 0..9 ohne 4 oder 6.

So würde ich es machen

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

Wie der geschätzte Herr Skeet betont hat:
Wenn n die Anzahl der zufällig ausgewählten Zahlen ist, die Sie auswählen möchten, und N der gesamte Stichprobenraum der zur Auswahl verfügbaren Zahlen ist:

1. Wenn n << N , sollten Sie nur die von Ihnen ausgewählten Nummern speichern und eine Liste überprüfen, um festzustellen, ob die ausgewählte Nummer darin enthalten ist.
2. Wenn n ~ = N , sollten Sie wahrscheinlich meine Methode verwenden, indem Sie eine Liste mit dem gesamten Probenraum füllen und dann bei der Auswahl Zahlen daraus entfernen.

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

Es gibt eine andere Möglichkeit, mit LFSR "zufällige" geordnete Zahlen zu erstellen. Schauen Sie sich Folgendes an:

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

Mit dieser Technik können Sie die geordnete Zufallszahl nach Index ermitteln und sicherstellen, dass die Werte nicht dupliziert werden.

Dies sind jedoch keine WAHREN Zufallszahlen, da die Zufallsgenerierung deterministisch ist.

Aber je Ihrem Fall können Sie diese Technik verwenden , um die Menge der Verarbeitung auf Erzeugung von Zufallszahlen zu reduzieren , wenn schlurfenden verwenden.

Hier ein LFSR-Algorithmus in Java (ich habe ihn an einen Ort gebracht, an den ich mich nicht erinnere):

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

Ein weiterer Ansatz, mit dem Sie angeben können, mit wie vielen Zahlen Sie möchten sizeund mit welchen minund maxWerten die zurückgegebenen Zahlen

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

Um es zu verwenden, werden 7 Zahlen zwischen 0 und 25 zurückgegeben.

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

Dies wäre viel einfacher in java-8:

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

Der effizienteste und einfachste Weg, sich nicht wiederholende Zufallszahlen zu erhalten, wird durch diesen Pseudocode erklärt. Es ist nicht erforderlich, verschachtelte Schleifen oder Hash-Lookups zu haben:

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

Angenommen, die erste durch Iteration erzeugte Zufallszahl 3 beginnt (von 0 bis 19). Dies würde Ergebnisse [0] = Mapping [3] ergeben, dh den Wert 3. Wir würden dann Mapping [3] 19 zuweisen.

In der nächsten Iteration betrug die Zufallszahl 5 (von 0 bis 18). Dies würde Ergebnisse [1] = Mapping [5] ergeben, dh den Wert 5. Wir würden dann Mapping [5] 18 zuweisen.

Angenommen, die nächste Iteration wählt erneut 3 (von 0 bis 17). Ergebnissen [2] würde der Wert von Mapping [3] zugewiesen, aber jetzt ist dieser Wert nicht 3, sondern 19.

Der gleiche Schutz bleibt für alle Nummern bestehen, auch wenn Sie fünfmal hintereinander dieselbe Nummer erhalten haben. Wenn der Zufallszahlengenerator Ihnen beispielsweise fünfmal hintereinander 0 geben würde, wären die Ergebnisse: [0, 19, 18, 17, 16].

Sie würden nie zweimal dieselbe Nummer bekommen.

Das Generieren aller Indizes einer Sequenz ist im Allgemeinen eine schlechte Idee, da dies viel Zeit in Anspruch nehmen kann, insbesondere wenn das Verhältnis der zu wählenden Zahlen MAXgering ist (die Komplexität wird dominiert von O(MAX)). Dies wird schlimmer, wenn sich das Verhältnis der zu wählenden Zahlen zu MAXeins nähert, da dann das Entfernen der gewählten Indizes aus der Folge aller ebenfalls teuer wird (wir nähern uns O(MAX^2/2)). Bei kleinen Zahlen funktioniert dies jedoch im Allgemeinen gut und ist nicht besonders fehleranfällig.

Das Filtern der generierten Indizes mithilfe einer Sammlung ist ebenfalls eine schlechte Idee, da einige Zeit für das Einfügen der Indizes in die Sequenz aufgewendet wird und der Fortschritt nicht garantiert ist, da dieselbe Zufallszahl mehrmals gezeichnet werden kann (aber groß genug MAXist dies unwahrscheinlich ). Dies kann nahezu komplex sein
O(k n log^2(n)/2), da die Duplikate ignoriert werden und angenommen wird, dass die Sammlung einen Baum für eine effiziente Suche verwendet (jedoch mit erheblichen konstanten Kosten kfür die Zuweisung der Baumknoten und möglicherweise für die Neuverteilung ).

Eine andere Möglichkeit besteht darin, die Zufallswerte von Anfang an eindeutig zu generieren, um sicherzustellen, dass Fortschritte erzielt werden. Das heißt, in der ersten Runde wird ein zufälliger Index in [0, MAX]generiert:

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

In der zweiten Runde wird nur [0, MAX - 1]generiert (da bereits ein Element ausgewählt wurde):

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)

Die Werte der Indizes müssen dann angepasst werden: Wenn der zweite Index in die zweite Hälfte der Sequenz fällt (nach dem ersten Index), muss er erhöht werden, um die Lücke zu berücksichtigen. Wir können dies als Schleife implementieren und so eine beliebige Anzahl eindeutiger Elemente auswählen.

Für kurze Sequenzen ist dies ein ziemlich schneller O(n^2/2)Algorithmus:

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
}

Wo n_select_numist Ihr 5 und n_number_numist Ihr MAX. Das n_Rand(x)gibt zufällige ganze Zahlen in [0, x](einschließlich) zurück. Dies kann etwas beschleunigt werden, wenn viele Elemente (z. B. nicht 5, sondern 500) ausgewählt werden, indem die binäre Suche verwendet wird, um die Einfügemarke zu finden. Dazu müssen wir sicherstellen, dass wir die Anforderungen erfüllen.

Wir werden eine binäre Suche mit dem Vergleich durchführen, n + j < rand_num[j]der der gleiche ist wie
n < rand_num[j] - j. Wir müssen zeigen, dass dies rand_num[j] - jimmer noch eine sortierte Sequenz für eine sortierte Sequenz ist rand_num[j]. Dies lässt sich glücklicherweise leicht zeigen, da der niedrigste Abstand zwischen zwei Elementen des Originals rand_numeins ist (die generierten Zahlen sind eindeutig, sodass immer ein Unterschied von mindestens 1 besteht). Wenn wir gleichzeitig die Indizes jvon allen Elementen subtrahieren, sind die Indexunterschiede
rand_num[j]genau 1. Im "schlimmsten" Fall erhalten wir also eine konstante Sequenz - die jedoch niemals abnimmt. Die binäre Suche kann daher verwendet werden und ergibt einen O(n log(n))Algorithmus:

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

Und schlussendlich:

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
}

Ich habe dies an drei Benchmarks getestet. Zuerst wurden 3 Zahlen aus 7 Elementen ausgewählt und ein Histogramm der ausgewählten Elemente wurde über 10.000 Läufe akkumuliert:

4265 4229 4351 4267 4267 4364 4257

Dies zeigt, dass jedes der 7 Elemente ungefähr gleich oft ausgewählt wurde und keine offensichtliche Verzerrung durch den Algorithmus verursacht wird. Alle Sequenzen wurden auch auf Richtigkeit (Eindeutigkeit des Inhalts) überprüft.

Der zweite Benchmark umfasste die Auswahl von 7 Zahlen aus 5000 Artikeln. Die Zeit mehrerer Versionen des Algorithmus wurde über 10.000.000 Läufe akkumuliert. Die Ergebnisse werden in Kommentaren im Code als bezeichnet b1. Die einfache Version des Algorithmus ist etwas schneller.

Der dritte Benchmark umfasste die Auswahl von 700 Zahlen aus 5000 Artikeln. Die Zeit mehrerer Versionen des Algorithmus wurde erneut akkumuliert, diesmal über 10.000 Läufe. Die Ergebnisse werden in Kommentaren im Code als bezeichnet b2. Die binäre Suchversion des Algorithmus ist jetzt mehr als zweimal schneller als die einfache.

Die zweite Methode ist schneller für die Auswahl von mehr als ca. 75 Elementen auf meinem Computer (beachten Sie, dass die Komplexität beider Algorithmen nicht von der Anzahl der Elemente abhängt MAX).

Es ist erwähnenswert, dass die obigen Algorithmen die Zufallszahlen in aufsteigender Reihenfolge erzeugen. Es wäre jedoch einfach, ein weiteres Array hinzuzufügen, zu dem die Zahlen in der Reihenfolge gespeichert werden, in der sie generiert wurden, und diese stattdessen zurückzugeben (zu vernachlässigbaren zusätzlichen Kosten O(n)). Es ist nicht notwendig, die Ausgabe zu mischen: das wäre viel langsamer.

Beachten Sie, dass sich die Quellen in C ++ befinden. Ich habe kein Java auf meinem Computer, aber das Konzept sollte klar sein.

EDIT :

Zur Unterhaltung habe ich auch den Ansatz implementiert, der eine Liste mit allen Indizes generiert
0 .. MAX, sie zufällig auswählt und aus der Liste entfernt, um die Eindeutigkeit zu gewährleisten. Da ich ziemlich hoch gewählt habe MAX(5000), ist die Leistung katastrophal:

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

Ich habe den Ansatz auch mit einer set(einer C ++ - Sammlung) implementiert , die beim Benchmark tatsächlich an zweiter Stelle b2steht und nur etwa 50% langsamer ist als der Ansatz mit der binären Suche. Dies ist verständlich, da setein Binärbaum verwendet wird, bei dem die Einfügekosten der binären Suche ähnlich sind. Der einzige Unterschied besteht in der Möglichkeit, doppelte Elemente zu erhalten, was den Fortschritt verlangsamt.

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

Der vollständige Quellcode ist hier .

Sie können eine der Klassen verwenden, die die Set-Schnittstelle ( API ) implementieren , und dann jede von Ihnen generierte Zahl mit Set.add () einfügen.

Wenn der Rückgabewert falsch ist, wissen Sie, dass die Nummer bereits zuvor generiert wurde.

Anstatt dies alles zu tun, erstellen Sie ein LinkedHashSetObjekt und Zufallszahlen nach Math.random()Funktion .... Wenn ein doppelter Eintrag auftritt, LinkedHashSetfügt das Objekt diese Nummer nicht zu seiner Liste hinzu ... Da in dieser Sammlungsklasse keine doppelten Werte zulässig sind. Am Ende erhalten Sie eine Liste von Zufallszahlen ohne doppelte Werte ....: D.

Ihr Problem scheint sich zu verringern, wenn Sie zufällig k Elemente aus einer Sammlung von n Elementen auswählen. Die Collections.shuffle-Antwort ist somit korrekt, aber wie bereits erwähnt ineffizient: ihr O (n).

Wikipedia: Fisher-Yates-Shuffle hat eine O (k) -Version, wenn das Array bereits vorhanden ist. In Ihrem Fall gibt es kein Array von Elementen, und das Erstellen des Arrays von Elementen kann sehr teuer sein, z. B. wenn max 10000000 statt 20 wäre.

Der Shuffle-Algorithmus umfasst das Initialisieren eines Arrays der Größe n, wobei jedes Element seinem Index entspricht, das Auswählen von k Zufallszahlen für jede Zahl in einem Bereich, wobei das Maximum kleiner als der vorherige Bereich ist, und das Vertauschen von Elementen gegen Ende des Arrays.

Sie können dieselbe Operation in O (k) -Zeit mit einer Hashmap ausführen, obwohl ich zugebe, dass dies eine Art Schmerz ist. Beachten Sie, dass sich dies nur lohnt, wenn k viel kleiner als n ist. (dh k ~ lg (n) oder so), andernfalls sollten Sie den Shuffle direkt verwenden.

Sie verwenden Ihre Hashmap als effiziente Darstellung des Hintergrundarrays im Shuffle-Algorithmus. Elemente des Arrays, die dem Index entsprechen, müssen nicht in der Karte angezeigt werden. Auf diese Weise können Sie ein Array der Größe n in konstanter Zeit darstellen. Es wird keine Zeit für die Initialisierung aufgewendet.

1. Wählen Sie k Zufallszahlen: Die erste liegt im Bereich von 0 bis n-1, die zweite von 0 bis n-2, die dritte von 0 bis n-3 usw. bis nk.

2. Behandeln Sie Ihre Zufallszahlen als eine Reihe von Swaps. Der erste zufällige Index wechselt zur endgültigen Position. Der zweite Zufallsindex wechselt zur vorletzten Position. Anstatt jedoch gegen ein Backing-Array zu arbeiten, sollten Sie gegen Ihre Hashmap arbeiten. Ihre Hashmap speichert jedes Element, das nicht in Position ist.

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

Der folgende Code erstellt eine Sequenz-Zufallszahl zwischen [1, m], die zuvor nicht generiert wurde.

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

Es gibt einen Algorithmus für den Kartenstapel: Sie erstellen eine geordnete Reihe von Zahlen (der "Kartenstapel") und wählen in jeder Iteration eine Zahl an einer zufälligen Position aus (wobei Sie natürlich die ausgewählte Zahl aus dem "Kartenstapel" entfernen).

Hier ist eine effiziente Lösung für die schnelle Erstellung eines zufälligen Arrays. Nach der Randomisierung können Sie einfach das n-te Element edes Arrays auswählen , inkrementieren nund zurückgeben e. Diese Lösung hat O (1) zum Erhalten einer Zufallszahl und O (n) zum Initialisieren, aber als Kompromiss erfordert sie eine gute Menge an Speicher, wenn n groß genug wird.

Es gibt eine effizientere und weniger umständliche Lösung für Ganzzahlen als eine Collections.shuffle.

Das Problem ist dasselbe wie das sukzessive Auswählen von Elementen nur aus den nicht ausgewählten Elementen in einem Satz und das Ordnen dieser Elemente an einem anderen Ort. Dies ist genau so, als würde man zufällig Karten austeilen oder Gewinnspielkarten aus einem Hut oder einer Tonne ziehen.

Dieser Algorithmus funktioniert zum Laden eines beliebigen Arrays und zum Erreichen einer zufälligen Reihenfolge am Ende des Ladens. Es funktioniert auch zum Hinzufügen zu einer Listensammlung (oder einer anderen indizierten Sammlung) und zum Erreichen einer zufälligen Reihenfolge in der Sammlung am Ende der Hinzufügungen.

Dies kann mit einem einzelnen Array erfolgen, das einmal erstellt wurde, oder mit einer numerisch geordneten Sammlung, z. B. einer Liste. Für ein Array muss die anfängliche Arraygröße genau der Größe entsprechen, die alle beabsichtigten Werte enthält. Wenn Sie nicht wissen, wie viele Werte im Voraus auftreten können, funktioniert auch die Verwendung einer numerisch geordneten Auflistung, z. B. einer ArrayList oder Liste, bei der die Größe nicht unveränderlich ist. Es funktioniert universell für ein Array jeder Größe bis zu Integer.MAX_VALUE, das etwas mehr als 2.000.000.000 beträgt. Listenobjekte haben dieselben Indexgrenzen. Ihr Computer verfügt möglicherweise nicht über genügend Arbeitsspeicher, bevor Sie zu einem Array dieser Größe gelangen. Es kann effizienter sein, ein in die Objekttypen eingegebenes Array zu laden und es nach dem Laden des Arrays in eine Sammlung zu konvertieren. Dies gilt insbesondere dann, wenn die Zielsammlung nicht numerisch indiziert ist.

Dieser Algorithmus erzeugt genau wie geschrieben eine sehr gleichmäßige Verteilung, bei der keine Duplikate vorhanden sind. Ein Aspekt, der SEHR WICHTIG ist, ist, dass das Einfügen des nächsten Elements bis zur aktuellen Größe + 1 möglich sein muss. Für das zweite Element könnte es daher möglich sein, es an Position 0 oder Position 1 zu speichern Für das 20. Element könnte es möglich sein, es an einem beliebigen Ort von 0 bis 19 zu speichern. Es ist genauso gut möglich, dass das erste Element an Ort 0 bleibt, wie es an einem anderen Ort landet. Es ist genauso gut möglich, dass der nächste neue Artikel irgendwohin geht, einschließlich des nächsten neuen Standorts.

Die Zufälligkeit der Sequenz ist so zufällig wie die Zufälligkeit des Zufallszahlengenerators.

Dieser Algorithmus kann auch verwendet werden, um Referenztypen an zufällige Stellen in einem Array zu laden. Da dies mit einem Array funktioniert, kann es auch mit Sammlungen funktionieren. Das bedeutet, dass Sie die Sammlung nicht erstellen und dann mischen oder in beliebiger Reihenfolge der eingefügten Objekte bestellen müssen. Die Sammlung muss nur die Möglichkeit haben, ein Element an einer beliebigen Stelle in der Sammlung einzufügen oder anzuhängen.

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

Es hängt wirklich alles davon ab, wofür Sie die zufällige Generierung benötigen, aber hier ist meine Meinung.

Erstellen Sie zunächst eine eigenständige Methode zum Generieren der Zufallszahl. Achten Sie darauf, Grenzwerte zu berücksichtigen.

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

Als Nächstes möchten Sie eine sehr einfache Entscheidungsstruktur erstellen, die Werte vergleicht. Dies kann auf zwei Arten erfolgen. Wenn Sie nur eine sehr begrenzte Anzahl von Zahlen überprüfen müssen, reicht eine einfache IF-Anweisung aus:

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

Das Obige vergleicht int1 mit int2 bis int5 und stellt sicher, dass die Zufälle keine Nullen enthalten.

Mit diesen beiden Methoden können wir Folgendes tun:

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

Gefolgt von:

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

Wenn Sie eine längere Liste überprüfen müssen, führt eine komplexere Methode zu besseren Ergebnissen sowohl bei der Klarheit des Codes als auch bei der Verarbeitung von Ressourcen.

Hoffe das hilft. Diese Seite hat mir so sehr geholfen, dass ich mich verpflichtet fühlte, zumindest zu versuchen, auch zu helfen.

Ich habe ein Snippet erstellt, das keine doppelte zufällige Ganzzahl generiert. Der Vorteil dieses Snippets besteht darin, dass Sie ihm die Liste eines Arrays zuweisen und auch das zufällige Element generieren können.

Keine doppelte Zufallsgeneratorklasse

Am einfachsten ist es, nano DateTime als Langformat zu verwenden. System.nanoTime ();