Hallo Leute,

weil es so viel Spass macht gleich noch ein Post.

Nein im Ernst, nachdem ich schon mehrere Wochen vergeblich nach einer vernünftigen Lösung suche wie man eine x-stellige positive ganze Zahl per Random erzeugt, in der dann auch noch jede Ziffer von 0 bis 9 nur einmal vorkommt dachte ich ich poste diese Frage mal hier. Das wird bestimmt andern Programmieren auch weiterhelfen.

Gruß Olli

[Gottzilla]

Hab ich das richtig verstanden

x-Stellig, also z. B.

64684
241243234123
23131
5

zahl von 0 - 9 nur einmal (was dann gleichzeitig wieder auf 10 Stellen begrenzen würde)

1234567890 = darf sein
22 = darf nicht sein

oder doch anders?

Genau so.

Führende Null darf auch sein, allerdings darf die Zahl nicht negativ sein.
Aber das wäre ja mit nextInt(0,limit) schon geklärt.

[Murray]

Normalerweise würde man (Pseudo-)Zufallszahlen ja mit der Klasse java.util.Random erzeugen. Hier geht es aber nicht wirklich um Zufallszahlen, sondern darum, eine zufällige Anzahl von Zeichen aus dem Vorrat '0'..'9' in eine zufällige Reihenfolge zu bringen.

Ein m.E. schöner Ansatz wäre eine Analogie zum Kartenmischen - nicht die Angebermethode mit den zwei Stapeln, die man dicht nebeneinanderlegt und dann daumenkinoartig ineinander verschränkt, auch nicht die Grobmotorikervariante, bei der man alle Karten auf den Tischen fallen lässt und dann mit der Hand durcheinandermischt (Loriot lässt grüßen), sondern ganz einfach: die eine Hand hält den Stapel, die andere nimmt eine zufällige Anzahl Karten von oben ab und schiebt sie unter den Rest.

Also:
Baue eine String aus den Ziffern '0' bis '9'. Das kann man entweder als String-Konstante machen (einfach, effizient, langweilig), oder in einer Schleife dynamisch erzeugen (eindeutig der höhere Geek-Faktor).

Dann wird eine Zufallszahl n erzeugt, die die Anzahl der Vermischungen angibt.

Dann läuft eine for-Schleife, in der n-mal der String analog zum Kartenmischen vermischt wird: teile den String an einer beliebigen Stelle und vertausche die Reihenfolge der beiden Teile.

Zum Schluss wird noch eine Zufallzahl l zwischen 1 und 10 bestimmt, die die Länge der Zahl bestimmt. Nimmt nun die ersten l Zeichen des Strings und mach daraus mit Integer.parseInt eine Zahl.

Voila!

(Das ist bestimmt kein besonders effizienter Algorithmus, aber doch irgendwie charmant)

[pago]

PHP-Code:

public static int random(int precision) {
    if(precision < 1 || precision > 9) throw new IllegalArgumentException("Precision must be between 1 and 9, but is "+precision);

    // Number generation (numberList = {n : 1 <= n <= 9})
    List<Integer> numberList = new ArrayList<Integer>();
    for(int i = 0; i < 10; i++) numberList.add(i);
        
    // Get an instance of random
    Random rand = new Random();
    
    // start algorithm
    int randomNumber = 0;
    for(int i = 0; i < precision; i++) {
        int index = rand.nextInt(numberList.size());
        int number = numberList.get(index);
        numberList.remove(index);
        randomNumber += number * Math.pow(10, i);
    }
    return randomNumber;
} 


Ungetestet.
Theorie: Wir zerlegen die Zahl in ihre Bestandteile und errechnen den Wert jeder einzelnen Stelle in der Form n*10^x.

Beispiel:

x = 0;
i = 2; n = rand() = 5
=> x += 5 * 10^2 = 5 * 100 = 500
i = 1; n = rand() = 1
=> x += 1 * 10^1 = 10 => x = 510
i = 0; n = rand() = 3
=> x += 3 * 10^0 = 3 => x = 513

Durch die Verwendung der Liste sollte jede Zahl nur einmal vorkommen können.


Edit: Ok... quote- und code-BBCode zu verwechseln ist nun wirklich selten dämlich. Nun kann man's hoffentlich entziffern.

@Murray

Ich find ja die Idee an sich super und einfallsreich, aber ist das nicht ein wenig wie das Rad neu erfinden. Wie würde es denn aussehen, wenn wir die Zahl einfach mit der Random Klasse erzeugen und dann auf unsere Kriterien hin überprüfen. Werden diese nicht erfüllt, fällt sie durch.

Das wäre so meine Idee, allerdings hab ich dafür noch keinen Source.

Gruß Olli

[pago]

Also meine Idee gefällt mir eigentlich.

Beim überprüfen der Zahl müsstest du sie wohl zwangsläufig in einen String umwandeln und unglaublich häßliche Spielchen veranstalten. Außerdem ist das mit Sicherheit eine Variante, die (im schlimmsten Fall) zu einer Endlosschleife führen kann - wer garantiert dir denn, dass du jemals per Zufall eine Zahl bekommst, die die Kriterien erfüllt?

Ja da hast du wohl recht. Ich werde das gleich mal probieren.

Posting war nicht an dich. Sorry, war zu langsam beim schreiben.

Also, der Code an sich funktioniert fast.

int number = numberList.get(index);

das wird nicht funktionieren da der return Wert von .get ja Object ist.
ne Idee?

[pago]

Ich hatte es für Java 5 geschrieben (d.h. mit Generics).

Die Version für < 5 sieht so aus:

PHP-Code:

public static int random(int precision) { 
    if(precision < 1 || precision > 9) throw new IllegalArgumentException("Precision must be between 1 and 9, but is "+precision); 

    // Number generation (numberList = {n : 1 <= n <= 9}) 
    List numberList = new ArrayList(); 
    for(int i = 0; i < 10; i++) numberList.add(new Integer(i)); 
         
    // Get an instance of random 
    Random rand = new Random(); 
     
    // start algorithm 
    int randomNumber = 0; 
    for(int i = 0; i < precision; i++) { 
        int index = rand.nextInt(numberList.size()); 
        int number = ((Integer)numberList.get(index)).intValue();
        numberList.remove(index); 
        randomNumber += number * Math.pow(10, i); 
    } 
    return randomNumber; 
} 


Hey funktioniert super,

allerdings produziert das System ab und zu eine Zahl die um eine Stelle kleiner ist als die angegebene Anzahl Stellen. Es ist aber kein System dahinter zu erkennen.

[Murray]

Zitat von Oliver

Wie würde es denn aussehen, wenn wir die Zahl einfach mit der Random Klasse erzeugen und dann auf unsere Kriterien hin überprüfen. Werden diese nicht erfüllt, fällt sie durch.

Dazu hat Pago ja schon etwas geschrieben. Es ist zwar ziemlich unwahrscheinlich, dass es wirklich zu einer Endlosschleife kommt, aber m.E. ist es schlimm genug, dass so ein Algorithmus ein nichtdeterministisches Laufzeitverhalten an den Tag legt - man kann nicht vorhersagen, wie lange es dauern wird.

Gerade bei großen Zahlen ist die Wahrscheinlichkeit doch recht hoch, dass die Zahl durchfallen wird (wie hoch, kann sicherlich ein Mathematiker bzw. Statistiker ausrechnen).

Zu meinem Algorithmus (der natürlich nicht so effizient ist wie der von Pago beim Implementieren merkt man, dass das Mischen nicht so funktioniert, wie ich das geschrieben habe; vielmehr zieht die eine Hand einen zufälligen Stapel aus der Mitte und legt ihn nach oben oder unter.

Implementieren lässt sich das so:

java.util.Random r = new java.util.Random();
	StringBuilder sb = new StringBuilder();
	for ( char c='0'; c <= '9'; c++) sb.append( c);
	
	for ( int j=0; j<10; j++) {
		int shuffle = r.nextInt( 9) + 2; //-- 2-10 Vertauschungen
		String s = sb.toString();
		for ( int i=0; i<shuffle; i++) {
			int pos1 = r.nextInt(4)+1; //--- 1..4
			int pos2 = r.nextInt(4)+5; //--- 5..9
			String s1 = s.substring( 0, pos1);
			String s2 = s.substring( pos1, pos2+1);
			String s3 = s.substring( pos2+1, s.length());
			s = s1 + s3 + s2;
		}
		int len = r.nextInt( 10) +1; //--- 1..10
		long l = Long.parseLong( s.substring( 0, len));
		System.out.println( "shuffle: " + shuffle + ",len: " + len + " -> " + l);
	}

[Murray]

Zitat von Oliver

allerdings produziert das System ab und zu eine Zahl die um eine Stelle kleiner ist als die angegebene Anzahl Stellen. Es ist aber kein System dahinter zu erkennen.

Das wird immer dann passieren, wenn als erste Ziffer die '0' verwendet wird.

[pago]

Zitat von Oliver

Hey funktioniert super,

allerdings produziert das System ab und zu eine Zahl die um eine Stelle kleiner ist als die angegebene Anzahl Stellen. Es ist aber kein System dahinter zu erkennen.

Ah. Klar, hab ich übersehen. Doch, da steckt ein System dahinter: Immer dann, wenn "number" gleich 0 ist, fehlt eine Stelle, weil:
0 * 10^x = 0

Hmm... Lösungsansatz ist nicht so besonders toll... wenn "number" = 0 ist, dann müssen wir statt 0 eine 10 verwenden. Bei der nächsten Zahl müssen wir dann 1*10^(x+1) abziehen.

PHP-Code:

public static int random(int precision) {  
    if(precision < 1 || precision > 9) throw new IllegalArgumentException("Precision must be between 1 and 9, but is "+precision);  

    // Number generation (numberList = {n : 1 <= n <= 9})  
    List numberList = new ArrayList();  
    for(int i = 0; i < 10; i++) numberList.add(new Integer(i));  
          
    // Get an instance of random  
    Random rand = new Random();  
      
    // start algorithm  
    int randomNumber = 0;
    boolean wasZero = false;
    for(int i = 0; i < precision; i++) {  
        int index = rand.nextInt(numberList.size());  
        int number = ((Integer)numberList.get(index)).intValue(); 
        numberList.remove(index);
        if(number == 0) {
            number = 10;
        }
        randomNumber += number * Math.pow(10, i);  
        if(number == 10) {
            wasZero = true;
        } else if(wasZero) {
            wasZero = false;
            randomNumber -= Math.pow(10, i-1);
        }
    }  
    return randomNumber;  
} 


So müsste es theoretisch funktionieren - außer ich hab wieder nen Sonderfall vergessen.

Du hast eigentlich nichts vergessen. Deine letzten Änderungen haben sich so ausgewirkt, das das Programm nun 5 Stellige Zahlen generiert. Wir müssen es also nur abfangen, dass es eine führende Null gibt oder diese mit ausgegeben wird.

[Gottzilla]

Dann überprüf halt einfach vor der Ausgabe ob das ding 9 oder 10 Stellen hat. Bei 9 Stellen kommt noch ne 0 vornedran, bei 10 bleibt se so wie se is.

ich würde ich die Ziffern von 0-9 shuffeln und dann einfach die ersten x rausnehmen...

PHP-Code:

    private static int zufallszahl(int stellen) {
        if(0>=stellen||stellen>9) throw new IllegalArgumentException();
        List<Integer> ziffern = new ArrayList<Integer>();
        for(int i=0;i<10;i++) ziffern.add(Integer.valueOf(i));
        Collections.shuffle(ziffern);
        int result = 0;
        // wenn die erste ziffer eine 0 ist, dann starten wir bei 1!
        int startindex = 0;
        if(0==ziffern.get(0).intValue()){
            startindex=1;
            ziffern.add(Integer.valueOf(0)); // damit die ggf. vorkommt
        }
        for(int i=startindex; i<stellen+startindex; i++){
            result = 10 * result + ziffern.get(i).intValue();
        }
        return result;
    }