# math Random zu zulosung ohne Zurücklegen



## sunwalker (18. Februar 2010)

Hier ihr.
Ich habe folgendes Problem. 
In meinem code kommt es zu einem Stackoverflow wegen einer Rekursion. aber hier erstmal der code

```
public class random {

    /**
     * @param args the command line arguments
     */
    int[] spielerAnz = new int[60];
    int spAnz;


    public static void main(String[] args) {
        // TODO code application logic here
        
        
        // 6 Spieler sollen gelost inhalt des arrys ist ja erstmal egal
        
        String[] s = new String[6];
        new random(s);

    }

    // Konst.
    public random(String[] spieler)
    {
        // Kleiner ausgabe test
        
        spAnz = spieler.length;
         for(int i=0; i<spAnz; i++)
        {
             int nrTest = wuerfle();
             
             System.out.println(nrTest);
             
         }
    }

    // Rekursive Funktion 
    public int wuerfle()
    {
        int nr = (int) ((Math.random()*spAnz)+1);

        if(test(nr))
        {
            wuerfle();
        }
        if(test(nr) == false)
        {
            schreibe(nr);

            return nr;
        }
        return 0;
    }

    // Testet ob die zahl schon im arry steht wenn ja wird true zurück gegeben
    public boolean test (int test)
    {
        for(int i=0; i<spielerAnz.length; i++)
        {
            if(spielerAnz[i] == test)
            {
                return true;
            }
        }
        return false;
    }



    // schreibt die zahl ins array 
    public boolean schreibe(int wurf)
    {
        for(int i=0; i<spielerAnz.length; i++)
        {
            if(spielerAnz[i] == 0)
            {
                spielerAnz[i] = wurf;
                return true;
            }
        }
        return false;
    }
}
```

wie ich mir denke liegt das daran das wer zu oft würfeln muss bis er ne zahl findet die net im array steckt.
gibts da ne möglichkeit des zu umgehen oder hab ich nen andern fehler gemacht ?

mfg schonmal Sun


----------



## Vereth (18. Februar 2010)

Diese kleine Beispielprogramm soll dir eine Anregung sein, wie so etwas schnell und sicher realisiert werden kann.
Und verwende das nächste mal bitte die java-Tags.

```
public void ziehung()
{
  int[] lotto = new int[49];
  int i    ; // Schleifenzähler
  int idx  ; // der Index der gezogenen Zahl
  int num  ; // die gezogene Zahl
  int limit; // die Anzahl der verfügbaren Zahlen

  // Initialisierung der Ziehungszahlen
  for ( i = 0; i < lotto.length; i++ )
  { lotto[i] = i+1; }
  // Ziehen und ausgeben der 6 Zahlen
  for ( i = 0, limit = lotto.length; i < 6; i++ )
  { 
    // Es wird zufällig eine Zahl gezogen
    idx = (int) (Math.random()*limit);
    num = lotto[idx];
    // limit wird erniedrigt, weil nun eine Zahl weniger zu Verfügung steht
    limit--;
    // die gezogene Zahl und die letzte Zahl tauschen den Platz
    // dadurch kann die letzte Zahl das nächste Mal auch noch gezogen werden
    // und die gezogene Zahl kommt in den Bereich der nicht verfügbaren Zahlen
    lotto[idx] = lotto[limit];
    lotto[limit] = num;
    // Ausgabe der gezogenen Zahl
    cout "gezogen: " << num << endl;
  }
}
```


----------



## Andibert (18. Februar 2010)

```
cout "gezogen: " << num << endl;
```
Hab ich da was verpasst?
cout in Java?
Spass bei Seite.
Super Beitrag

MfG
Andibert


----------



## lui7172 (20. Februar 2010)

Unabhängig davon, dass Vereth Dir eine wesentlich elegantere Lösung aufgezeigt hat, möchte ich Dir zu Deinem Code ein paar Hinweise geben. Denn zum lernen ist es vlt. gar nicht schlecht. Der Hauptschwachpunkt ist die Methode wuerfle(), denn sie wird so lange rekursiv aufgerufen, bis sie eine Zahl gewürfelt hat, die nicht schon mal gewürfelt wurde. Das wird nach hinten hin natürlich immer schwieriger. Aber unabhängig davon ist eine Rekursion hier überhaupt nicht nötig, ok, ist sie nie, aber hier ist sie nicht mal hilfreich. 

Aber fangen wir noch etwas früher an:

```
if(test(nr))
		{
			wuerfle();
		}
		if(test(nr) == false)
		{
			schreibe(nr);

			return nr;
		}
```

Wenn test(nr) false liefert, dann testest Du noch mal. Den zweiten Test ersparst Du Dir mit


```
if(test(nr))
		{
			wuerfle();
		} else {
			schreibe(nr);

			return nr;
		}
```

So, hier nun die iterative Variante - womit sich das schon wieder erledigt hat 


```
public int wuerfle_iterativ()
	{
		int nr;
		do {
			nr = (int) ((Math.random()*spAnz)+1);
		} while( test(nr) );
		
		schreibe(nr);
		return nr;
	}
```

Eine gute Lösung ist dies aber noch lange nicht. Denn es werden ja immer noch ggf. sehr viele Zahlen gezogen, bis endlich eine den Test nicht besteht.


----------



## Thomas Darimont (20. Februar 2010)

Hallo,

ich würds so machen:

```
package de.tutorials;

import java.util.BitSet;
import java.util.Random;

public class RandomDrawExample {

	public static void main(String[] args) {
		Random random = new Random();
		BitSet alreadyTaken = new BitSet();
		
		int nums = 49;
		int itemsToDraw = 6;
		int i = 0;
		
		while (i < itemsToDraw) {
			int candidate = random.nextInt(nums) + 1;

			if (!alreadyTaken.get(candidate)) {
				System.out.println(candidate);
				alreadyTaken.flip(candidate);
				i++;
			}
			
		}
	}
}
```

Gruß Tom


----------



## lui7172 (20. Februar 2010)

Der Vorteil von Vereth Algo liegt darin, dass er auf jeden Fall in 6 Runden zum Ergebnis führt. In Deinem Fall kommt es beim ziehen von 6 Zahlen mit einer Gesamtwahrscheinlichkeit von 15/49 zu einer "Kollision" und es muss erneut gezogen werden. 
D.h, mit durchschnittlich 6,3 Ziehungen ist man hier am Ziel. Ist das so richtig?

Gruß
lui


----------



## Vereth (21. Februar 2010)

Ein weiterer Vorteil ist, dass er in-place arbeitet und deswegen keinen zusätzlichen Speicher vebraucht. Die Elemente sind nachher natürlich etwas durcheinander, aber wenn man sich die Resultate merkt (was der Normalfall ist), kann man danach die ursprünliche Ordnung leicht wieder herstellen, indem man in umgekehrter Reichenfolge wieder zurück-swappt. Man kann das sogar rekursiv implementieren!


----------



## Anime-Otaku (22. Februar 2010)

Ich finde eher Thomas Algorithmus am Besten.

1. Durch Benutzung der Random Klasse ist die Wahrscheinlichkeit geringer, dass die gleiche Zahl nochmal kommt, anstatt benutzen von Math.random
2. Durch das BitSet ist einfach und performant abgelegt, ob diese Zahl bereits gezogen ist.

Update:
Da stimme ich Thomas auch zu...
3. Es ist einfacher zu verstehen 

Naja es führen viele Wege zum Ziel


----------



## Thomas Darimont (22. Februar 2010)

3. Ist einfacher zu verstehen (IMHO).

Wobei ich den limit-Trick ziemlich clever finde ;-)

Gruß Tom


----------



## Vereth (22. Februar 2010)

Anime-Otaku hat gesagt.:


> 1. Durch Benutzung der Random Klasse ist die Wahrscheinlichkeit geringer, dass die gleiche Zahl nochmal kommt, anstatt benutzen von Math.random


Wieso das? Aber ich sehe ein, dass die Random-Klasse einfacher zu handhaben ist.


Anime-Otaku hat gesagt.:


> 2. Durch das BitSet ist einfach und performant abgelegt, ob diese Zahl bereits gezogen ist.


Das BitSet ist für manchen etwas gewöhnungsbedürftig, aber eigentlich leicht zu verwenden. Performant kann man es hinsichtlich des sparsamen Speicherverbrauchs nennen, aber in diesem Algorithmus ist es fehl am Platz, denn es verhindert keine Doppelziehungen. Wenn aus n Mannschaften n/2 Paarungen zu ermitteln sind, dann muss man im Mittel 2n Ziehungen durchführen. Effizient nenne ich das nicht. Mein Algorithmus kommt ohne BitSet o.ä. aus, weil er in-place arbeitet und nur diejenigen berücksichtigt, die noch nicht gezogen wurden.

Und was einfacher zu verstehen ist, ist Geschmacksfrage.

Spaßeshalber habe ich hier noch eine rekursive Fassung, die auch Aufräumarbeiten erledigt. 


```
public void zieheZahlen()
{
  int[] lotto = new int[49];

  for ( int i = 0; i < lotto.length; i++ )
  { lotto[i] = i+1; }
  Random rnd = new Random();
  ziehung(lotto,6,rnd)
}

public void ziehung(int[] lotto, int limit, Random rnd)
{
  int idx  ; // der Index der gezogenen Zahl
  int num  ; // die gezogene Zahl
  
  if ( limit <= 0 ) return;
  // Es wird zufällig eine Zahl gezogen
  idx = rnd.nextInt(limit);
  num = lotto[idx];
  lotto[idx] = lotto[limit];
  lotto[limit] = num;
  // Ausgabe der gezogenen Zahl
  System.out.println ( "gezogen: " + num );
  // Ziehung der nächsten
  ziehung(lotto,limit-1,rnd);
  // Aufräumen
  lotto[limit] = lotto[idx];
  lotto[idx] = num;
}
```


----------



## Anime-Otaku (22. Februar 2010)

Vereth hat gesagt.:


> Wieso das? Aber ich sehe ein, dass die Random-Klasse einfacher zu handhaben ist.



Bei Math.random wird auch die Random Klasse verwendet. Dieser ist jedoch *global* gültig und arbeitet auf double Zahlen. Die sind natürlich wesentlich genauer, d.h. mehr Möglichkeiten, dass die gleiche Ganzzahl herauskommt.


----------



## Vereth (22. Februar 2010)

Das ist ein Trugschluss. Jeder Zufallszahlen-Generator muss eine Gleichverteilung aufweisen.


----------



## lui7172 (24. Februar 2010)

Anime-Otaku hat gesagt.:


> Ich finde eher Thomas Algorithmus am Besten.
> 
> 1. Durch Benutzung der Random Klasse ist die Wahrscheinlichkeit geringer, dass die gleiche Zahl nochmal kommt, anstatt benutzen von Math.random
> 2. Durch das BitSet ist einfach und performant abgelegt, ob diese Zahl bereits gezogen ist.
> ...



Zu 1.) Verstehe ich nicht.

Zu 2.) Du nimmst die Verwendung einer performanten Klasse als Argument für den Einsatz eines Algos, dessen Laufzeit im konkreten nicht vorhergesagt werden kann? Thomas seine Lösung kann auch durchaus 100000 Zahlen ziehen müssen bis er am Ziel ist. OK, unwahrscheinlich (mag ich jetzt nicht ausrechnen), aber nicht auszuschließen. 

Zu 3.) Sehe ich nicht so. Aber ist wohl "Geschmackssache".


----------

