/*
Datei............: Aufg1123.java
Projekt..........: Einführung in die Java-Programmierung
Erstellt.........: 21.11.97, Guido Krüger
Geändert.........: --
Aufgabe..........: Musterlösung zu Aufgabe 11.23
Kommentare.......:

Im Kurstext befindet sich natürlich bereits eine Lösung für
dieses Problem. Daß diese Aufgabe dennoch ausgewählt wurde,
liegt daran, daß es noch eine andere, etwas ungewöhnliche
Lösung gibt. Sie entstammt dem (sehr lesenswerten) Buch
"Programming Pearls" von John Bentley (Column 11) und wurde
ihrerseits durch Donald Knuth's "The Art of Computer Programming",
Vol 2, inspiriert (Kapitel 3.4.2), der seinerseits auf einen
Beitrag aus der "Communications Of The ACM" aus dem Jahre 1962
verweist. 

Das Problem besteht darin, aus der Menge der ganzen Zahlen
von 1 bis N genau M unterschiedliche in sortierter Reihenfolge
auszugeben. Für M = 6 und N = 49 entspricht dies genau dem
gewünschten Lottotip. Eine interessante Lösung, die für kleine
N gut geeignet ist, besteht nun darin, nacheinander alle
Zahlen von 1 bis N zu durchlaufen und dabei jeweils zu
überprüfen, ob ein Fließkomma-Zufallswert zwischen 0 und 1
kleiner ist als der Quotient aus der Anzahl noch nicht 
ausgewählter Zahlen und der Anzahl noch nicht besuchter
Zahlen. 

In unserem Beispiel wird also zunächst die Zahl 1 besucht und
geprüft, ob eine erzeugte Zufallszahl kleiner als 6/49 ist.
Ist dies der Fall, geht es mit der 2 weiter und die neue
Zufallszahl wird gegen 5/48 getestet. War der erste Test 
dagegen nicht erfolgreich, so wird die zweite Zufallszahl
gegen 6/48 getestet. Dieses Verfahren liefert immer genau
6 Zahlen aus dem Bereich von 1 bis 49. Falls bereits vor Ende
der Schleife 6 Zahlen ausgewählt wurden, ist der Bruch 0 und
es wird keine weitere Zahl gewählt, da die nächste Zufallszahl
niemals kleiner 0 wird. Sind noch x Zahlen nicht durchlaufen
und müssen ebenfalls noch x Zahlen ausgewählt werden, ergibt
der Bruch 1, und es werden alle folgenden Zahlen ausgewählt. 

Der Algorithmus sieht auf den ersten Blick nicht sehr
vertrauenerwckend aus. Es dauert eine Weile, bis man erkennt,
daß in jedem Fall genau M Zahlen ausgewählt werden. Mit 
einem kleinen Beweis über die bedingten Wahrscheinlichkeiten
zur Auswahl der Zahlen 1 bis N kann nachgewiesen werden, daß
alle Zahlen gleich wahrscheinlich sind.
*/
import java.util.*;

public class Aufg1123
{
  public static void main(String args[])
  {
	for (int i = 0; i < 5; ++i) {
	  printMOutOfN(6, 49);
	  try {
		Thread.sleep(300);
	  } catch (InterruptedException e) {
		//nothing to do
	  }
	}
  }

  static void printMOutOfN(int m, int n)
  {
	Random rnd = new Random(System.currentTimeMillis());
	int select = m;
	for (int i = 1; i <= n; ++i) {
	  if (rnd.nextDouble() < ((double)select / (n - i + 1))) {
		System.out.print(i + " ");
		--select;
	  }
	}
	System.out.println();
  }
}