Hilfe, doppelte Zufallszahlen

[Lyd]

Guten Abend,

ich wollte ien Programm schreiben dasein Array mit Zufallszahlen (die nicht doppelt vorkommen dürfen)füllt. Ich weiß nicht wo der Fehler steckt?
Es kommen immernoch doppelte Zahölen raus.

	public static void Nummern (int N){
		
		int [] a = new int [N];
		
		for (int i = 0; i<N; i++){
			a[i] = (int)((Math.random()*N)+1);
			for (int j = 0; j< N; j++){
		if (a[i]==a[j] && i!= j){
			a[i]=(int)((Math.random()*N)+1);
			j = 0;
			System.out.print(a[i]);
			}
		}
		}
		
	}

 

[Haave]

Naja, wenn ich mal umgangssprachlich zusammenfassen darf, was dein Code macht:
"Hey Math.random(), gib mir mal ne Zufallszahl!" "Okay, hier eine 8 für dich." "Hmm, eine 8 hab ich aber schon. Gib mir ne neue Zahl." "Okay, hier hast du eine 8." "Gut, das passt!"

Was ich damit sagen will: Du prüfst nur einmal, ob die Zahl doppelt ist, und lässt dann eine neue generieren. Nach dem zweiten Generieren wird einfach nur noch abgenickt und die Zahl übernommen, auch wenn zufällig die gleiche Zahl nochmal generiert wurde.

 

[jDennis79]

Wofür ist die zweite for-Schleife? Ihr Sinn erschließt sich mir gerade nicht wirklich, und ich vermute mal ganz stark, dass da auch der Fehler liegt.

 

[Murray]

Die zweite Schleife soll das machen, was Haave vermisst, nämlich prüfen, ob der Zufallswert schon irgendwo im Array an einer anderen Stelle auftaucht. Prinzipiell kann das so auch klappen, aber
1. j muss auf -1 gesetzt werden und nicht auf 0, weil das j++ vor dem nächsten Durchlauf ausgeführt wird (und man will wieder ganz von vorn prüfen)
2. sollte die Ausgabe der Zufallszahl erst am Ende der äußeren Schleife passieren.

 

[timbeau]

Ich würde ne eigene Methode schreiben, die Zufallsvariablen ausgibt und die du solange aufrufst bis sie dir eine passende zurückliefert.

 

[Murray]

Ein Problem bei diesem Ansatz ist, dass es gerade bei der Verteilung der letzten Zahlen jede Menge Fehlversuche gibt. So gibt es für die letzte Ziffer ja nur noch eine Möglichkeit; trotzdem wird "geraten", bis man zufällig die eine erwischt. Mit der Anzahl der Zahlen steigt auch die Wahrscheinlichkeit, dass die Laufzeit gegen unendlich geht.
Ein besseres Laufzeitverhalten könnte man bekommen, indem man das Array einfach fortlaufend mit den zu verteilenden Zahlen füllt (dann kann es keine doppelten geben) und dann eine feste Anzahl von Vertauschungen macht, indem man z.B zwei Indizes per Random ermittelt und dann die entsprechenden Werte vertauscht.
Man kann zum Vertauschen natürlich auch Collections.shuffleverwenden, aber das ist bei Hausaufgaben vielleicht nicht immer zulässig.

 

[timbeau]

Ja, wenn man eine Ebene tiefer geht nimmt man auch lieber ne HashMap o.ä.

 

[faetzminator]

Ja, wenn man eine Ebene tiefer geht nimmt man auch lieber ne HashMap o.ä.

Also ich würde eher zu einem [c]HashSet<Integer>[/c] raten.
Da allerdings die Zahlen 0-(N-1) verwendet werden, kannst du diese auch in eine [c]List<Integer>[/c] abfüllen und [c]Collections.shuffle(List)[/c] drüber laufen lassen.

 

[timbeau]

Deshalb o.ä.

Sonst können wir ja direkt in den Security Bereich gehen ;-)

 

[faetzminator]

Man könnte meinen, dass mir langweilig wär... Sogar noch mit einer dritten Lösung...:

public static List<Integer> getRandomNumbers(int n, int max) {
    if (max < n) {
        throw new IllegalArgumentException("max < n");
    }
    List<Integer> list;
    if (max == n) {
        list = getData(n);
    } else if (max <= n * 2) {
        list = getSmallMaxData(n, max);
    } else {
        list = getBigMaxData(n, max);
    }
    Collections.shuffle(list);
    return list;
}

protected static List<Integer> getData(int n) {
    List<Integer> list = new ArrayList<Integer>(n);
    for (int i = 0; i < n; i++) {
        list.add(i);
    }
    return list;
}

protected static List<Integer> getBigMaxData(int n, int max) {
    Set<Integer> set = new HashSet<Integer>();
    while (set.size() < n) {
        set.add((int) (Math.random() * max));
    }
    return new ArrayList<Integer>(set);
}

protected static List<Integer> getSmallMaxData(int n, int max) {
    List<Integer> list = getData(max);
    while (list.size() > n) {
        list.remove((int) (Math.random() * list.size()));
    }
    return list;
}

 

[timbeau]

Das hat mich jetzt mal interessiert und ich hab ein wenig getestet und deine Methode mit meiner verglichen.

Ich selber verwende diesen Code:

static HashSet<Integer> getRandomNumbersHash(int randomCounter, int maxNumber) {
        HashSet<Integer> hs = new HashSet<Integer>();
        SecureRandom secureR = new SecureRandom();
        if(maxNumber < randomCounter){
            throw new IllegalArgumentException("max < n");
        }
        while(hs.size() < randomCounter){
            hs.add(secureR.nextInt(maxNumber));
        }
        return hs;
    }

Dann hab ich ne kurze Testklasse geschrieben und verschiedene Größen ausgewählt.
Bei > ca. 50.000 Zahlen verweigert die List-Methode ihren Dienst bei mir.
Ich habe allerdings den Zahlenraum der Zufallszahlen immer auf Anzahl * 2 gesetzt. Eventuell ist das ausschlaggebend.

Ausgabe:
testHashsetBig() mit Anzahl = 500000
Dauer ca.: 1 Sek bzw. 1928 Millisekunden.
XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX


testHashsetBig() mit Anzahl = 50000
Dauer ca.: 0 Sek bzw. 237 Millisekunden.
testListBig() mit Anzahl = 50000
Dauer ca.: 2 Sek bzw. 2865 Millisekunden.


testHashsetMedium() mit Anzahl = 10000
Dauer ca.: 0 Sek bzw. 15 Millisekunden.
testListMedium() mit Anzahl = 10000
Dauer ca.: 0 Sek bzw. 159 Millisekunden.


testHashsetSmall() mit Anzahl = 100
Dauer ca.: 0 Sek bzw. 0 Millisekunden.
testListSmall() mit Anzahl = 100
Dauer ca.: 0 Sek bzw. 1 Millisekunden.

 

[Marco13]

Ist wohl das gleiche wie in http://www.java-forum.org/java-basi...ablen-miteinander-vergleichen.html#post612775 oder...?

 

[timbeau]

Jo, stimmt

0x7F800000´s Lösung ist ja hardcore (Hes a robot)

Die letzte Lösung erscheint mir mit ähnlichen Problemen behaftet wie meine, bei zu kleiner Differenz zwischen Größe des Sets und Raum der Zufallszahlen. Bei dieser wird zum Ende hin sehr häufig die Zufallszahl inkrementiert um zu passen odeR?

 

[Marco13]

Es hat wohl O(k*n), aber dafür ist es sehr "einfach" (im dort im Thread angedeuteten Sinn) ....