Zufallsausgabe

[Daniel Thoma]

Hallo Don,

rand:    0    1    2    3    4    5    6     7     8     9
Anzahl: 952 2103 3456 4745 6532 8447 10874 14272 19249 29370
Wie man sieht, steigt die Wahrscheinlichkeit für einen bestimmten rand-Wert mit dessen Größe stark an. Von Gleichverteilung kann da absolut nicht die Rede sein.

Doch, Du betrachtest nur die falschen Werte. Ich halte im forderen Teil des Arrays die schon ausgewählten Elemente, und im hinteren Teil die, aus denen noch ausgewählt werden kann.
Aus denen noch wählbaren Elementen wird jedes mal mit gleicher Wahrscheinlichkeit gezogen. Dadurch, dass das immer weniger werden und sie sich im hinteren Teil befinden, werden die rand-Werte natürlich immer größer, das spielt aber keine Rolle.
Mein Algorithmus macht im Prinzip etwas sehr ähnliches, wie Deiner. Du wählst immer zufällig eine noch leere Stelle aus, während ich immer zufällig ein noch nicht verwendetes Element auswähle.

Meine Funktion dagegen ergab für 2 Millionen Durchläufe im Schnitt 24,00359 Vertauschungen, bis eine bestimmte Permutation erreicht war. Hier war die Abweichung von der Theorie also 10 mal kleiner. Allerdings ist meine Lösung auch deutlich langsamer.

Den unterschied würde ich auf unterschiedliche Auswirkung nummerischer Fehler zurückführen. Mit perfekten, reellen Zufallszahlen sind beide wählen beide Algorithmen Permutationen perfekt gleicherteilt. Nun sind Floating-Point-Zahlen aber natürlich diskretisiert. Dadurch wird es gewisse Fehler geben.

Wenn Du die Güte der Algorithmen vergleichen willst, solltest Du aber sowieso nicht die Anzahl der Vertauschungen zählen, sondern die Häufigkeit von Permutationen zählen.
Nimm vielleicht ein paar mehr Elemente (so 6 bis 8 gehen noch) und zähle die Häufigkeit, mit der die verschiedenen Permutationen vorkommen.

Ich hab das mal kurz mit Java ausprobiert:

  
private static Random random = new Random();  
  
    public static void main(String[] argv) {  
        int limit = 10000000;  
        Map<String, Integer> permutations = new HashMap<String, Integer>();  
        for (int i = 0; i < limit; ++i) {  
            int[] array = new int[] {0, 1, 2, 3, 4, 5, 6};  
            shuffle(array);  
            String s = Arrays.toString(array);  
            Integer count = permutations.get(s);  
            if (count == null) {  
                count = 0;  
            }  
            ++count;  
            permutations.put(s, count);  
            if (i % 100000 == 0) {  
                System.out.println(i);  
            }  
        }  
        double d = (double) limit / (double) factorial(7);  
        double error = 0;  
        String perm = "";  
        double errorSum = 0;  
        for (Map.Entry<String, Integer> entry: permutations.entrySet()) {  
            double e = Math.abs(d - (double) entry.getValue());  
            if (e > error) {  
                error = e;  
                perm = entry.getKey();  
            }  
        }  
        System.out.println();  
        System.out.println("max abs error: " + error);  
        System.out.println("avg abs error: " + errorSum / (double) limit);  
        System.out.println("max rel error: " + error / d);  
        System.out.println("avg rel error: " + errorSum / d / (double) limit);  
    }  
  
    public static void shuffle(int[] array) {  
        for (int i = 0; i < array.length; ++i) {  
            int r = i + (int) Math.floor(random.nextDouble() * (array.length - i));  
            int t = array[i];  
            array[i] = array[r];  
            array[r] = t;  
        }  
    }  
  
    public static int factorial(int i) {  
        int r = 1;  
        for (int j = 2; j <= i; ++j) {  
            r *= j;  
        }  
        return r;  
    }  

Ergebnisse bei mir: (mit 7 Elementen und 10 Mio. aufrufen)
max abs error: 166.8730158730159
avg abs error: 0.0
max rel error: 0.08410400000000001
avg rel error: 0.0

Das sieht doch ziemlich gut aus. Um auch die maximale Abweichung noch kleiner zu bekommen, bräuchte man wohl noch mehr durchläufe.

Grüße

Daniel