math Random zu zulosung ohne Zurücklegen

[sunwalker]

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]

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]

 cout "gezogen: " << num << endl;

Hab ich da was verpasst?
cout in Java?
Spass bei Seite.
Super Beitrag

MfG
Andibert

 

[lui7172]

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]

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]

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]

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]

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]

3. Ist einfacher zu verstehen (IMHO).

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

Gruß Tom

 

[Vereth]

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.

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