Produceți în mod determinist o matrice de indici bazați pe numărul de intrare

Vă rugăm să consultați secțiunea de referințe de mai jos pentru termeni.

Există o metodă unidirecțională cunoscută pentru a produce o matrice de indici, bazată doar pe două elemente de intrare:

• lungimea tabloului rezultat
• număr, folosit ca o cheie pentru a produce în mod determinist matricea

Dacă există doar o metodă care poate produce numai matrice de lungime fixă ​​- poate fi și un început bun pentru mine.

Exemple:

Referinţă:

• un matrice de indici:
  Matrice, ale cărei valori sunt toate numere întregi de la 0 la (lungimea tabloului - 1), neordonată.
• determinat funcţie:
  O funcție, care produce același rezultat de fiecare dată când sunt furnizate aceleași date de intrare

Începeți cu o serie de indici sortați.

The Durstenfeld Shuffle funcționează prin trecerea prin matrice, tratând o parte a matricei ca fiind amestecată și restul matricei ca ne-amestecate. Pur și simplu schimbă fiecare dintre elementele din matrice cu un element aleatoriu din regiunea neamestecate până când matricea este amestecată complet.

Toate permutările vor fi echiprobabile.

Un CSPRNG determinist (însămânțat cu numărul dvs. de intrare) este utilizat pentru a genera indici aleatori selectați în timpul amestecării.

const csprng = new csprng(<numărul de intrare seed>);
const len ​​= 10;
const a = new Array(len);
for(fie i=0; i<len; i++) a[i] = i;

for(lasa i=0; i<len; i++) {
  let swapIndex = nextDeterministicallyRandomIntBetween(i, len, csprng);
  fie tmp = a[i]; a[i] = a[swapIndex]; a[swapIndex] = tmp; // schimb
}

function nextDeterministicallyRandomIntBetween(lowerBoundInclusive, 
    upperBoundExclusive, csprng) {

  returnează lowBoundInclusive +
    nextDeterministicallyRandomIntLowerThan(upperBoundExclusive-lowerBoundInclusive, csprng);
}

function nextDeterministicallyRandomIntLowerThan(upperBoundExclusive, csprng) {
  // determinăm numărul minim de biți „b” necesar pentru a reprezenta
  // (upperBoundExclusive-1). Apoi cereți în mod repetat csprng pentru b biți
  // până când returnează un rezultat mai mic decât upperBoundExclusive
  fie b = Math.ceil(Math.log(upperBoundExclusive) / Math.log(2));
  fie r;
  face {
    r = csprng.nextBits(b);
  } while (r>=upperBoundExclusive);
  întoarce r;
}