Zufallswiedergabe Probleme

Software
36

Mich hatten noch zwei Sachen an der Lösung gewurmt:

  1. Die do-while-Schleife ist unschön, da sie manchmal (gerade bei nur wenigen Tracks in einem Ordner) bis zu 60 mal durchlaufen werden muss. Der Grund ist, dass das zugegebenermaßen trickreiche Ermitteln einer geeigneten Primzahl ist optimal ist. Besser wäre es, eine Primzahl zu finden, die möglichst noch näher an der jeweiligen Trackanzahl liegt, oder aber man findet einen Weg, die do-while-Schleife vollständig einzusparen.
  2. Fast alle aufeinanderfolgenden Tracks haben denselben Abstand. Ich bin mir nicht sicher, ob das in jedem Fall hinreichend zufällig wirkt.

Für beides habe ich jetzt eine Lösung gefunden.

Zum Einen kann die do-while-Schleife durch eine einzige Modulo-Operation ersetzt werden wenn bestimmte Fälle vorher abgefangen wurden. Damit ist es nicht mehr nötig, eine möglichst kleine Primzahl zu wählen und ich setze die Primzahl daher fest auf 257.

Zum Anderen kann ich noch die Zahl der erzeugbaren Permutationen vervielfachen, indem ich das Bitmuster einer generierten Zahl mit einem initial zufällig gewählten aber dann festen Bitmuster per XOR durcheinanderwürfele. Das ergibt dann zwangsläufig wieder eine Permutation derselben Zykluslänge, bei der nun aber die Differenzen aufeinanderfolgender Werte nicht mehr so einheitlich sind. Man muss nur gewährleisten, dass das most significant bit (MSB) des verwendete Bitmuster kleiner ist als das der Trackanzahl. Das ist aber (ohne aufwändiges Errechnen des MSBs) gewährleistet, wenn man das Bitmuster einer Zufallszahl nimmt, die maximal halb so groß ist wie die Zahl der Tracks.

Zusammen ergibt das dann den folgenden Code:

Initialisierung (beim Auflegen der Karte):

firstTrack = random(numTracksInFolder) + 1;
periodLength = 257;
step = random(1, numTracksInFolder);
currentPos = random(numTracksInFolder);
currentTrack = firstTrack;
xorMask = random(numTracksInFolder >> 2);

Anwählen des nächsten Tracks:

currentPos = (currentPos + step) % periodLength;
if (currentPos >= numTracksInFolder) {
    currentPos = step - (periodLength - currentPos - 1) % step - 1;
}

currentTrack = (currentPos ^ xorMask + firstTrack - 1) % numTracksInFolder + 1;

Anwählen des vorhergehenden Tracks:

currentPos = (currentPos + periodLength - step) % periodLength;
if (currentPos >= numTracksInFolder) {
    currentPos = numTracksInFolder - step + (currentPos - numTracksInFolder) % step;
}

currentTrack = (currentPos ^ xorMask + firstTrack - 1) % numTracksInFolder + 1;

Damit erhält man eine zufällige von mehr als N(N-1)N/2 Permutationen mit geringem konstantem Zeitaufwand pro Schritt.