Recursive Function

[Taff]

Hallo,

als erstes, bitte verzeiht mein Deutsch, als zweites mein Java

Ich wollte ganz gerne ein "recursive function" bauen um ein Zahl zu generieren, nach zu schauen ob dieses Zahl bereits in ein Array vorhanden ist, falls nein, füge die hinzu, falls nicht rufe meine Method erneut auf. Leider weiss ich nicht wie ich es anstelle.

[highlight=Java]
import java.util.Arrays;
public class generateNumbers {

private static int[] lotteryNumbers;

public static void main(String[] args) {

lotteryNumbers = new int[6];
for(int i=0; i<6; i++){
//Random number
int tmp = generateNumber();
//assign it to the array
lotteryNumbers= tmp;
}
}

//Hier kommen die Probleme
private static int generateNumber(){
//Generiere ein zufällige Zahl
double tmpDouble = Math.round(Math.random()*8);
//Konvertiere es in ein int
int tmp = (int)tmpDouble;
//Schaue ob die Zahl bereits vorhanden ist
int index = Arrays.binarySearch(lotteryNumbers, tmp);
//Rufe die gleich funktion erneut auf
if(index<0){
generateNumber();
}else{
//Falls vorhanden gib diesen Wert zurück.
return tmp;
}
}

}[/highlight]

Kann mir wer weiterhelfen?

Danke und Grüße aus HH

-Taff

 

[0x7F800000]

Hast du früher funktional programmiert, oder aus welchem grund willst du hier denn unbedingt eine rekursion verbauen? Nur mal so als Warnung: Java-Compiler können die Endrekursion nicht ordentlich handhaben, und müllen den Speicher zu, obwohl es nicht nötig wäre. D.h. wenn man zwei vollkommen äquivalente Konstrukte hat, einmal mit Rekursion, einmal mit Iteration gelöst, dann kann das sein, dass die Iteration läuft, während die Rekursion mit einem StackOverflowError endet
=> Wo es angebrachter ist, lieber Iteration vorziehen.

Zum Code:
[highlight=Java]
//Hier kommen die Probleme
[/highlight]
Damit kann keiner was anfangen, poste Fehlermeldung, oder erläutere zumindest was das Problem ist.


[highlight=Java]//Generiere ein zufällige Zahl
double tmpDouble = Math.round(Math.random()*8);
//Konvertiere es in ein int
int tmp = (int)tmpDouble;[/highlight]
Das ist alles unnötig kompliziert.
Besser:
[highlight=Java]
(new java.util.Random()).nextInt(8);
[/highlight]
...schaue mal in der API nach der Random Klasse, diese ist Math.random() praktisch immer vorzuziehen.


[highlight=Java]//Schaue ob die Zahl bereits vorhanden ist
int index = Arrays.binarySearch(lotteryNumbers, tmp);
//Rufe die gleich funktion erneut auf
if(index<0){
generateNumber();
}else{
//Falls vorhanden gib diesen Wert zurück.
return tmp;
}
}[/highlight]
Die Bedingung hast du grad um 180° umgedreht, findest du nicht?

 

[Taff]

Hi,

danke für dein Antwort.

Ich beschäftige mich mit Java seit ungefahr 1 Stunde, von daher sind tips wie deine, iteration vorzuziehen sehr willkommen.

Auch für den Tip mit der random danke ich dir. Ich hatte Math.random() von meine Flash Tage noch im Kopf.

Es gibt eigentlich kein "unbedingt" für die Rekursion, bin nur am spielen und solche Funktionalität ist immer gut zu lernen.

[highlight=Java]if(index<0){
generateNumber();
}else{
return tmp;
}[/highlight]

Der fehler ist das falls index<0 returned es kein int und deshalb (glaube ich) hätte der return wert void sein.

-Taff

 

[0x7F800000]

du hast da erstmal rein syntaktische fehler drin: die methode muss ja ein int zurückgeben, speziell muss sie sich selbst wieder aufrufen und das ergebnis natürlich mit return zurückgeben, also:

public static int f(){
if(blahblah<whatever){ return f(); }else{ return tmp; }
}

Zum anderen hast du nicht nachgedacht, bzw nicht in der API richtig gelesen. Binäre suche funktioniert nur auf monotonen Funktionen, d.h. dein Array muss immer sortiert vorliegen (das ist OK, da beim Lotto die reihenfolge egal ist, also dürfen wir jedes mal sortieren) Etwas unangenehmer wird die sache dadurch, dass das array anfangs mit nullen gefüllt wird, und diese immer nach "unten" sinken, während die großen Zahlen "oben rumschwimmen", das heißt man muss das array von "oben" auffüllen, damit es sinn macht.
Zu guter letzt muss ich mich selbst nochmal zitieren:

Die Bedingung hast du grad um 180° umgedreht, findest du nicht?

Bitte im code auf die entsprechende stelle achten.

Insgesamt könnte man es etwa so machen:
[highlight=Java]
public class _ {

private static int[] lotteryNumbers;

public static void main(String[] args) {

lotteryNumbers = new int[6];
for(int i=0; i<lotteryNumbers.length; i++){
lotteryNumbers[5-i]=generateNumber();
Arrays.sort(lotteryNumbers);
}
System.out.println(Arrays.toString(lotteryNumbers));
}

//Hier kommen die Probleme
private static int generateNumber(){
int temp=(new Random()).nextInt(49);
//Schaue ob die Zahl bereits vorhanden ist
if(Arrays.binarySearch(lotteryNumbers, temp)<0){
//Falls NICHT vorhanden gib diesen Wert zurück.
return temp;
}else{
//bereits vorhanden, andere zahl versuchen
return generateNumber();
}
}

}
[/highlight]

Davon ist aber wegen der erhöhten "Kryptizität" (wie heißt's auf deutsch?^^) und aus performancegründen abzuraten. Man sollte bei solchen Sachen lieber keine Arrays verwenden, dafür gibt's genug Collections. So ein Sample ohne zurücklegen lässt sich außerdem sehr viel schneller herstellen. In diesem Fall (6 von 49) läuft es noch relativ schnell.
Aber versuch mal mit deiner methode 999999 von 1000000 zufällige zahlen auszuwählen. Bei der letzten Zahl musst du drei jahre warten, bis der rechner zufällig auf eine der letzten beiden verbleibenden Möglichkeiten gestoßen ist. Aber das ist ein anderes Märchen....

 

[Taff]

Vielen, vielen Dank für deine Unterstützung.

[highlight=Java] public static int f(){
if(blahblah<whatever){ return f(); }else{ return tmp; }
}[/highlight]

Genau sowas wollte ich realisieren...zumindest bevor ich von die risiken wüsste.

Auch Collections wird ich unter der Lupe nehmen.

Nochmala danke für deine informative Post...und was "Kryptizität" auf Deutsch heißt...da fragst du leider der Falsche....ich bin Engländer

Ciao

Taff

 

[SchonWiederFred]

Hallo,
Ich wollte ganz gerne ein "recursive function" bauen um ein Zahl zu generieren, nach zu schauen ob dieses Zahl bereits in ein Array vorhanden ist, falls nein, füge die hinzu, falls nicht rufe meine Method erneut auf.

May I suggest a different approach?
Put the numbers from 1 to 49 in a list, shuffle the list, and then take the first six numbers as a result.

That solution is
a) guaranteed to terminate
b) maybe not as efficient as doing everything by hand, but how many lottery numbers do you need per second?
c) very easy to implement and thus less error-prone

import java.util.*;

public class Main
{
	public static List<Integer> lotteryNumbers()
	{
		List<Integer> numbers = new ArrayList<Integer>(49);
		for (int i = 1; i <= 49; ++i)
			numbers.add(i);
		Collections.shuffle(numbers);
		return numbers.subList(0, 6);
	}

	public static void main(String[] args)
	{
		System.out.println(lotteryNumbers());
	}
}

 

[Taff]

Thanks very much Fred.

I didn't even know about lists and collections yesterday. I think an arrayList is always going to win at the moment. It is very seldom that I have created an array in the past where the contents were only of one variable type AND I knew the size prior to populating, although lottery numbers could have been one

I'll take a look at

[highlight=Java] List<Integer> numbers = new ArrayList<Integer>(49);[/highlight]

syntax, which apparently quite different to what I have been doing up until now.

Thanks again for the follow-up.

Taff

 

[0x7F800000]

May I suggest a different approach?
Put the numbers from 1 to 49 in a list, shuffle the list, and then take the first six numbers as a result.

That solution is
a) guaranteed to terminate

that's allright...

b) maybe not as efficient as doing everything by hand, but how many lottery numbers do you need per second?

ouch! This is not about lotto-numbers. That's a very common problem.
That's only a coincidence, but just few month ago i had to simulate 50 years of german lotto.... ~1000 times! This was an exercise in stochastics, we had to check if the number 13 is somehow suspicious^^ In R such a simulation took 8 minutes, althought in R implementations of all this algorithms are *probably* optimal. So it does matter how to implement it. Your implementation always shuffles the whole collection. Just imagine the use case where your set contains n=1000000 elements, but you only want to pick k=1 or k=5 or something like that... You would waste very much time for shuffling the huge array. Shuffling runs in O(n), copying first k-element out of the array takes O(k), so this implementation runs in in O(n+k).

c) very easy to implement and thus less error-prone

that's true...

Here is how i probably would implement it for arrays:
[highlight=Java]
import java.util.*;

public class Sample {
/**
* creates for a set a random subset of specified size
* @param set set as array
* @param sizeOfSubset size of the wanted subset
* @return random subset with specified size
*/
public static int[] sample(int[] set, int sizeOfSubset){
int[] result=new int[sizeOfSubset];

int temp, index, n=Math.min(set.length-sizeOfSubset,sizeOfSubset);

Random random=new Random();
for(int i=0; i<n; i++){
//select random element from [0,set.length-1-i]
index=random.nextInt(set.length-i);
//swap it with the element on position set.length-1-i
temp=set[set.length-1-i];
set[set.length-1-i]=set[index];
set[index]=temp;
}

if(n!=sizeOfSubset){
System.arraycopy(set,0,result,0,sizeOfSubset);
}else{
System.arraycopy(set,set.length-sizeOfSubset,result,0,sizeOfSubset);
}
return result;
}

public static void main(String... _){

int[] set=new int[49];
for(int i=0; i<set.length; i++) set=i+1;

for(int i=0; i<20; i++){
System.out.println(Arrays.toString(sample(set,i)));
}
}
}
[/highlight]
notice the little optimization: if you want to pick more than a half of elements from the set, this method picks the elements that will not be included in the result-subset, and returns the remaining elements.

Not very complicated either, but runs in O(min(n/2,k)) where n is size of the set, and k the size of subset. For small k it behaves like O(k). Ok?