JavaScript Mit Wahrscheinlichkeit eins der ersten drei Array-Elemente zurückgeben

[CyborgBeta]

Hi! Ich hab erstmal die folgende Funktion:

function getRandomFromArray(a, creep) {
    if (a && a.length) {
        a.sort((a, b) => creep.pos.getRangeTo(a) - creep.pos.getRangeTo(b));
        let b = [];
        for (let i = 0; i < a.length && i < 3; i++) {
            let e = a[i];
            b.push(e);
        }
        return b[Math.floor(Math.random() * b.length)];
    }
    return null;
}

Das heißt, die Array-Elemente werten erst nach der kürzesten Distanz zum "Creep" (das ist ein Objekt auf einer Karte) sortiert und dann wird, sofern vorhanden, aus den ersten drei ein zufälliges Element zurückgegeben.

Das funktioniert auch ganz gut... dennoch möchte ich, dass mit einer Wahrscheinlichkeit von 50 % das erste Element zurückgegeben wird, und mit 33,3 % das zweite, und mit 16,6 % das dritte.

Gibt es nur zwei Elemente, so mit den Wahrscheinlichkeiten 66,6 % und 33,3 % das erste bzw. zweite Element...

Wie formuliere ich das am besten algorithmisch in JS/ES6/TS (so dass es dann auch für n Elemente gelten kann)?

Vielen Dank 😊

 

[madmax2010]

https://medium.com/developers-writing/fibonacci-sequence-algorithm-in-javascript-b253dc7e320e

klingt grob, als ob du dir fibonacci schnappen könntest und dann als Wahrscheinlichkeit für ein Element
prob = 1/fibonacci(n+1)
Ich sehe bei deinen Wahrscheinlichkeiten keine klare Verteilung. Aber es ist klar, dass du spätere Elemente mit einer geringeren Wahrscheinlichkeit ziehen willst

 

[Hancock]

Ist die Gewichtung immer n, n-1, n-2, ....1? Dann kannst du den kleinen Gauss anwenden. Die Anzahl aller Gewichte ist n*(n+1)/2, die Anzahl der Gewichte nach Element x ist x*(x+1)/2. Wenn wir das Pferd von Hinten aufzäumen, dann kann man durch den relativen Quotient das Lösen (Formel 2/Formel 1) https://www.wolframalpha.com/input?i=solve+x*(x+1)/(n*(n+1))=a+for+x .
Dein Index ist dann https://www.wolframalpha.com/input?i=plot+round(1/2*sqrt(4*x*3*4+1)-1)+from+0+to+1

let n=b.length;
let idx_r=round(0.5(Math.sqrt(4*Math.random()*n*(n+1)+1)+1));
let idx=n-idx_r-1;
return b[idx];

Oder natürlich klassisch ein Array erstellen und die Elemente gemäß ihrer Häufigkeit oft einfügen und dann daraus ziehen.

Ergänzung (11. Oktober 2022)

@madmax2010 Der Artikel lässt ja die analytische Lösung mit O(1) raus...

let fib=(x)=>{return (Math.pow((1+Math.sqrt(5))/2,x)-Math.pow((1-Math.sqrt(5))/2,x))/Math.sqrt(5);}

 

[CyborgBeta]

Hallo ihr, der Gauß-Ansatz gefällt mir sehr gut, ich wusste nicht, dass es auch eine "geschlossene Formel" dafür gibt... ich hatte zwar auch Stochastik, aber an der Stelle hab ich nicht so gut aufgepasst.

Ich werde später mal versuchen, es wie vorgeschlagen umzusetzen.

Ja, die vorderen Elemente sollen mit einer höheren Wahrscheinlichkeit zurückgegeben werden, und dabei ist die genaue Wahrscheinlichkeit gar nicht so wichtig, es soll nur gelten: p(a[i]) > p(a[i+1]), wenn p(...) die Wahrscheinlichkeit angibt, mit der das Element ... zurückgegeben werden soll... ( und natürlich: sum(p(a[i])) == 1 ).

Hoffe, man kann mein Geschreibsel verstehen. 😊

 

[Hancock]

sum(p(a)) == 1

Gilt immer, da du ja genau ein Element zurückgibts.

p(a) > p(a[i+1])

Dann kannst du auch richtig faul da ran gehen.

let rand=(x)=>{return Math.pow(Math.random(),x);}
let idx=Math.floor(rand(2)*b.length);

Für x>1 sind damit die vorderen Elemente häufiger. https://www.wolframalpha.com/input?i=plot+round(10*x^2)+from+0+to+1

"geschlossene Formel"

Die vom Gauss kann man schon kennen, hat ja ne nette Geschichte . Ich finde die geschlossene Fibonacci viel cooler, weil warum gibt was mit sqrt(5) was ganzzahliges, und wie kommt man drauf (Hinweis: Das ist viel lineare Algebra )

 

[CyborgBeta]

Dankeschön, genau so wünsche ich mir das 😊

function getRand(a) {
  if (a && a.length) {
    let rand = (x) => {
      return Math.pow(Math.random(), x);
    }
    let idx = Math.floor(rand(2) * a.length);
    return a[idx];
  }
  return null;
}

let a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let b = new Array(10).fill(0);

for (let i = 0; i < 1000; i++) {
  b[getRand(a) - 1]++;
}
let sum = 0;
for (let i = 0; i < b.length; i++) {
  b[i] = Math.round((b[i] / 1000 * 100) * 100) / 100;
  sum += b[i];
}
console.log(b, sum);

Ausgabe:
[29, 14.1, 12.3, 8.3, 8.3, 6.8, 4.7, 5.4, 6.7, 4.4], 100.00000000000001

Bei .floor(rand(2) * a.length) hatte ich erst überlegt, ob du nicht .floor(rand(2 * a.length)) meintest, aber alles gut...

Kann ich die Wahrscheinlichkeitsverteilung noch "strecken"/"ziehen" bzw. "stauchen"/"drücken"?

 

[Hancock]

Klar, einfach die 2 anpassen. Je größer, desto mehr Gewicht hat das erste Element.

 

[CyborgBeta]

Danke, funktioniert gut mit verschiedenen n und Anpassung des Parameters (2).

Dieses Thema ist gelöst (es sei denn, jemand möchte noch beweisen, warum das auch funktioniert).