RandomArrayGenerator

[HendrikSai]

Moin,

für eine Hausaufgabe soll ich einem zufällig generierten Array zwei zufällige Positionen tauschen. Das generieren hat des Arrays hat geklappt. Zwei Positionen zu tauschen bekomme ich dann leider nicht mehr hin... bei mir kann es auch sein, dass z.B. Pos3 mit Pos3 getauscht wird, also eig. nicht wirklich was getauscht wird. Wie verhindere ich diesen Fehler?
Mir ist klar, dass ich bei der Suche nach einer zweiten zufälligen Zahl das Array ohne "t1" betrachten muss, wüsste aber nicht wie ich das mache.

[CODE=java]public static int[] random(int size) { int count = 0; // Zaehler fuer Statistikzwecke am Anfang 0 int[] result = new int[size]; System.out.print("Zufällig generiertes Array: "); for (int i = 0; i < size; i++) { result[i] = (int)(Math.random() * size + 1); System.out.print(result[i] + " "); } while(count < size) { int tmp; int t1; int t2; Random r = new Random(); t1 = r.nextInt(result.length); Random p = new Random(); t2 = p.nextInt(result.length); tmp = result[t1]; result[t1] = result[t2]; result[t2] = tmp; System.out.println(""); for (int i = 0; i < size; i++) { System.out.print(result[i] + " "); } count++; } return result; }[/CODE]

 

[HendrikSai]

Okay ich habs dann doch nach mehreren Überlegungen herausgefunden... mit einer while schleife kann man das problem ziemlich einfach lösen... vll hilft das ja einigen mit ähnlichen problemen

while (result[t1] == result[t2]) {
t2 = p.nextInt(result.length);
}
tmp = result[t1];
result[t1] = result[t2];
result[t2] = tmp;

 

[ComFreek]

Mathematische Grundlagen

Angenommen deine Arrays haben Länge 4, dann möchtest du mathematisch gesehen einen Wert aus M({0,1,2,3}) = {(0, 1), (0, 2), (0, 3); (1, 0), (1, 2), (1, 3); (2, 0), (2, 1), (2, 3); (3, 0), (3, 1), (3, 2)} uniform samplen.
Allgemeiner: sei X eine Menge. Dann möchtest du einen Wert aus M(X) := X × X \ diag(X) uniform samplen, wobei diag(X) = {(x, x) : x in X} die Diagonale ist.

Wenn du M(X) konkret als Liste (nicht Menge) berechnen würdest (also z. B. M({0,1,2,3}) wie oben dargestellt), dann könntest du einen Wert uniform ganz einfach samplen: rand.nextInt(0, |M(X)| - 1).

Wir können uns die Berechnung aber auch sparen, indem wir (a) |M(X)| berechne (ohne M(X) zu berechnen) und (b) den Index rand.nextInt(0, |M(X)| - 1) bijektiv "on-the-fly" auf ein Element von M(X) abbilden (erneut: ohne M(X) zu berechnen).

a) |M(X)| = |X × X \ diag(X)| = |X|*|X| - |X| = |X|(|X| - 1)
b) Wir definieren die bijektive Funktion f: {0, ..., |M(X)| - 1} -> X × X \ diag(X) via f(i) = (g(i), h(i)) wobei

• g(i) = i / (|X|-1) uns die erste Komponente gibt (hier ist / truncated division)
• h(i) = let j = (i % (|X|-1) in if (j < g(i)) then j else j + 1 uns die zweite Komponente gibt und wobei j eine Hilfsvariable ist ("let ... = ... in" Statement inspiriert von funktionalen Programmiersprachen)

Für b) am besten das Anfangsbeispiel M({0,1,2,3}) betrachten. Die Funktion f ist dort implizit durch die gewählte Totalordnung in der Auflistung der Menge gegeben.

Implementierung der mathematischen Vorschriften

Obige mathematische Vorschriften kann man direkt so in jeder Programmiresprache implementieren, z. B. in JavaScript wie folgt (live auf Edit fiddle - JSFiddle - Code Playground):

function g(X, i) {
  return Math.floor(i / (X - 1));
}

function h(X, i) {
  const j = i % (X - 1);
  return (j < g(X, i)) ? j : j + 1;
}

function f(X, i) {
  return [g(X, i), h(X, i)];
}

function len(X) {
  return X * (X - 1);
}

const X = 4;
for (let i = 0; i < len(X); i++) {
  document.body.innerHTML += f(X, i) + "<br>";
}

Das gibt Folgendes wie gewünscht aus:

0,1
0,2
0,3
1,0
1,2
1,3
2,0
2,1
2,3
3,0
3,1
3,2

Hieran sieht man, dass f tatsächlich eine Bijektion auf die genau eingangs aufgezählte Menge M({0,1,2,3}).

Finale Implementierung: Samplen von uniform zufälligen Indexpaaren ungleicher Komponenten

Wir erweitern obige Implementierung noch um ein uniformes Samplen in {0, ..., |M(X)| - 1} und sind damit fertig (live auf Edit fiddle - JSFiddle - Code Playground):

/**
  * Samples a random integer in [min, max].
  * @soruce <https://stackoverflow.com/a/29246176/603003>
  * @author Lior Elrom <https://stackoverflow.com/users/1843451/lior-elrom>
  * @license <https://creativecommons.org/licenses/by-sa/4.0/>
  */
function randomInteger(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function sample(X) {
  return f(X, randomInteger(0, len(X) - 1));
}

const X = 4;
for (let i = 0; i < 15; i++) {
  document.body.innerHTML += sample(X) + "<br>";
}

 

[ComFreek]

while (result[t1] == result[t2]) {
  t2 = p.nextInt(result.length);
}

Ja, das was du machst, kann man auch machen. Das nennt sich Rejection Sampling. Der theoretische Nachteil ist, dass die reine Laufzeit unbegrenzt ist. Die probabilistisch erwartete Laufzeit ist jedoch begrenzt und praktisch funktioniert dieser Ansatz wunderbar.
Dieser Ansatz ist auch wesentlich einfacher zu implementieren als mein obiger -- wo man durchaus sich mal in Indizes vertun kann ("off by one").