Java-Generierung nicht wiederholende Zufallszahlen

Möchte ich erstellen Sie eine Reihe von Zufallszahlen ohne Duplikate in Java.

Zum Beispiel habe ich ein array zum speichern von 10.000 zufällige Ganzzahlen von 0 bis 9999.

Hier ist was ich habe, so weit:

import java.util.Random;
public class Sort{

    public static void main(String[] args){

        int[] nums = new int[10000];

        Random randomGenerator = new Random();

        for (int i = 0; i < nums.length; ++i){
            nums[i] = randomGenerator.nextInt(10000);
        }
    }
}

Aber der obige code erzeugt Duplikate. Wie kann ich sicherstellen, dass die Zufallszahlen nicht wiederholen?

mögliche Duplikate von eine eindeutige Zufallszahlen in Java
Aber wenn Sie zu entfernen, wiederholte zahlen, dann sind Sie nicht so random
Möchten Sie alle 10.000 zahlen im array in zufälliger Reihenfolge, oder wollen Sie 10.000 Zufallszahlen? weil Sie nicht haben, können 10.000 Zufallszahlen im Bereich von 0 - 9.999 (dann sind Sie nicht zufällig mehr)
Ja nur ich will Sie nicht wiederholen, dass ist das wichtigste.
Wollen Sie es nicht zu wiederholen, in der Art von "1 1 2" wiederholt? "1 2 1" eine akzeptable Sequenz?

InformationsquelleAutor Fernando Martinez | 2013-04-14

41
```
Integer[] arr = {...};
Collections.shuffle(Arrays.asList(arr));
```
Beispiel:
```
public static void main(String[] args) {
    Integer[] arr = new Integer[1000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = i;
    }
    Collections.shuffle(Arrays.asList(arr));
    System.out.println(Arrays.toString(arr));

}
```
Shuffle ist toll, aber zuerst sollten Sie erstellen Sie ein array enthält zahlen von 0 bis 9999 und dann mische es. Auch, was ist die Zeit-Komplexität von shuffle?
Ich erstellte array-und hergeschoben. Ich bin nicht sicher, aber ich denke mal die Komplexität der shuffle sollte O(n). Denn wenn nur tun swapping zufällig innerhalb eines Arrays.

InformationsquelleAutor Achintya Jha
7

Einen einfachen Algorithmus, die Ihnen Zufallszahlen ohne Duplikate können gefunden werden in dem Buch Programming Pearls p. 127.

Aufmerksamkeit: Das resultierende array enthält die Nummern in der Reihenfolge! Wenn Sie wollen, dass Sie in zufälliger Reihenfolge, die Sie haben, um den shuffle-array entweder mit Fisher–Yates-shuffle oder über eine Liste und rufen Collections.shuffle().

Der Vorteil dieses Algorithmus ist, dass Sie nicht brauchen, um ein array erstellen mit allen möglichen zahlen, und die Laufzeit-Komplexität ist immer noch linear O(n).
```
public static int[] sampleRandomNumbersWithoutRepetition(int start, int end, int count) {
    Random rng = new Random();

    int[] result = new int[count];
    int cur = 0;
    int remaining = end - start;
    for (int i = start; i < end && count > 0; i++) {
        double probability = rng.nextDouble();
        if (probability < ((double) count) / (double) remaining) {
            count--;
            result[cur++] = i;
        }
        remaining--;
    }
    return result;
}
```
Hinweis: (re: Eure "Aufmerksamkeit") Collections.shuffle ist dabei ein Fisher-Yates-shuffle, es ist also nicht ein "entweder-oder" - situation.
Sie haben Recht, die Collections.shuffle hat eine Fisher-Yates-shuffle, aber Sie brauchen eine List es zu benutzen. Arrays.asList muss das array als array vom Typ Integer statt int um die Konvertierung zu tun korrekt, dann müssen Sie nicht haben, um zusätzlichen Speicher zuweisen. Schreiben Sie die Fisher-Yates-shuffle selbst vermeidet Konvertierung und keine zusätzlichen Speicher erforderlich ist.
nur versuchen zu verstehen, warum probability < ((double) count) / (double) remaining benötigt wird? warum nicht füllen Sie das array von Anfang bis Ende und nur shuffle?

InformationsquelleAutor the

Achintya Ji hat die richtige Idee hier. Statt darüber nachzudenken, wie, um Duplikate entfernen, entfernen Sie die Fähigkeit für Duplikate erstellt werden, in den ersten Platz.

Wenn Sie wollen stick mit einem array von ints und wollen, mischen Sie Ihre Bestellung (manuell, was ganz einfach ist) gehen Sie folgendermaßen vor.

erstellen Sie ein array der Größe n.
Schleife durch und initialisieren Sie jeweils mit dem Wert an index i auf den Wert i (oder i+1, wenn Sie wollen, haben die zahlen von 1 bis n statt von 0 bis n-1).
schließlich in einer Schleife durch das array wieder tauschen für jeden Wert ein Wert an einer zufälligen index.

Könnte der code geändert werden, wie folgt Aussehen:

import java.util.Random;

public class Sort
{
    //use a constant rather than having the "magic number" 10000 scattered about
    public static final int N = 10000;

    public static void main(String[] args)
    {
        //array to store N random integers (0 - N-1)
        int[] nums = new int[N];

        //initialize each value at index i to the value i 
        for (int i = 0; i < nums.length; ++i)
        {
            nums[i] = i;
        }

        Random randomGenerator = new Random();
        int randomIndex; //the randomly selected index each time through the loop
        int randomValue; //the value at nums[randomIndex] each time through the loop

        //randomize order of values
        for(int i = 0; i < nums.length; ++i)
        {
             //select a random index
             randomIndex = randomGenerator.nextInt(nums.length);

             //swap values
             randomValue = nums[randomIndex];
             nums[randomIndex] = nums[i];
             nums[i] = randomValue;
        }
    }
}

Und wenn ich du wäre würde ich wahrscheinlich Pause jeder dieser Blöcke in separate, kleinere Methoden anstatt eine große main-Methode.

Hoffe, das hilft.

InformationsquelleAutor Benjamin Brumfield

2

Wenn Sie brauchen, erzeugen zahlen mit Intervallen, es ist nur so:
```
Integer[] arr = new Integer[((int) (Math.random() * (16 - 30) + 30))];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
Collections.shuffle(Arrays.asList(arr));
System.out.println(Arrays.toString(arr));`
```
Das Ergebnis:

[1, 10, 2, 4, 9, 8, 7, 13, 18, 17, 5, 21, 12, 16, 23, 20, 6, 0, 22, 14, 24, 15, 3, 11, 19]

Hinweis:

Wenn Sie brauchen, dass die null nicht lassen, könnten Sie einen "wenn"

InformationsquelleAutor Marcus person

Wie über dieses?

LinkedHashSet<Integer> test = new LinkedHashSet<Integer>();
Random random = new Random();
do{
    test.add(random.nextInt(1000) + 1);
}while(test.size() != 1000);

Kann der Benutzer dann Durchlaufen Sie die Set mit einer for-Schleife.

InformationsquelleAutor Jitin Kodian

0

In Java 8, wenn Sie möchten, um eine list nicht wiederholen N zufällige Ganzzahlen in range (a, b), wo b ist exklusiv, Sie können so etwas wie dies:
```
Random random = new Random();
List<Integer> randomNumbers = random.ints(a, b).distinct().limit(N).boxed().collect(Collectors.toList());
```
Das ist das äquivalent von "random.Ganzzahlen(a, b).boxed().distinct().mapToInt(ich -> ich).Grenze(N).boxed().sammeln(...)". Nicht zu eficient. Auch unter der Haube ist es das gleiche-Implementierung als Vaibhav Jain, erfordern 500500 Iterationen für 1000 Elemente. Bitte nehmen Sie sich die Zeit zu verstehen, die Bibliotheken, die Sie verwenden.
Tatsächlich, die Wahrscheinlichkeit zu finden, die richtige Zufallszahl, die bei jeder iteration ist gegeben durch (N-n+1)/N in der Vaibhav Jain-Implementierung. Wo N ist der insgesamt geforderte Anzahl von Zufallszahlen und n ist die Nummer der aktuellen iteration. Die erwartete Anzahl der Iterationen ist dann gegeben durch O(N log(N)), die im Durchschnitt weniger als 500500. Siehe en.wikipedia.org/wiki/Coupon_collector%27s_problem
Hey, das ist interessant. danke!

InformationsquelleAutor Slawomir Domagala

-1

public class Randoms {

static int z, a = 1111, b = 9999, r;

public static void main(String ... args[])
{
       rand();
}

    public static void rand() {

    Random ran = new Random();
    for (int i = 1; i == 1; i++) {
        z = ran.nextInt(b - a + 1) + a;
        System.out.println(z);
        randcheck();
    }
}

private static void randcheck() {

    for (int i = 3; i >= 0; i--) {
        if (z != 0) {
            r = z % 10;
            arr[i] = r;
            z = z / 10;
        }
    }
    for (int i = 0; i <= 3; i++) {
        for (int j = i + 1; j <= 3; j++) {
            if (arr[i] == arr[j]) {
                rand();
            }
        }

    }
}
}

InformationsquelleAutor jayanthanantharapu

-1

HashSet<Integer>hashSet=new HashSet<>();
Random random = new Random();
//now add random number to this set
while(true)
{
    hashSet.add(random.nextInt(1000));
    if(hashSet.size()==1000)
        break;
}

InformationsquelleAutor Vaibhav Jain

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.