Array mit einzigartigen Zufallszahlen füllen - wie geht das?

[fabbsen]

Hi ihrs,

ich will in einem vorgegebenen Bereich per Zufall Sterne auf der x-Achse platzieren. Allerdings sollen sich die Sterne möglichst nicht überlagern. Das Platzieren erfolgt über die Werte aus einem vorher definierten Array.

Wie kann ich nun in einer For-Schleife abfragen, ob es schon einen gleichen Zahlenwert gibt? Wenn möglich mit einer Toleranz von x Pixeln, da die Sterne einen bestimmten Durchmesser haben und sich möglichst nicht überlagern sollten.

Geht das - und wenn ja: Wie mach ich das am geschicktesten?

Meine "Füllfunktion" sieht folgendermaßen aus:

	stars_upper = [];
	for (j=0; j<18; j++) {
		stars_upper.push(randRange(655,1564));
	}

... wobei die Funktion randRange() einen Zufallswert innerhalb der Eckdaten als return-Wert hat.

Bin für Lösungen bzw. Lösungsansätze sehr dankbar.

Viele Grüße
der Fäb

[DaisyW]

Hallo Du,

vielleicht so irgendwie:

Array.prototype.containsItem = function(item) {
	for(var i=0;i < this.length; i++) {
		if (this[i] == item) return true;
	}
	return false;
}

stars_upper = new Array;
	for (j=0; j<18; j++) {
		var randNumber;
		do {
			randNumber = randRange(655,1564);
		} while (stars_upper.containsItem(randNumber));
		stars_upper.push(randNumber);
	}

Grüße,

Daisy

[fabbsen]

hi daisy - danke schonmal ...

das scheint zumindest zu verhindern, dass exakt die gleichen Werte entstehen - passt!

Wie kann ich jetzt am elegantesten noch eine Toleranz +/- 20 Pixel mit einbeziehen? Hast da noch ne Idee?

[DaisyW]

Zitat von fabbsen

Wie kann ich jetzt am elegantesten noch eine Toleranz +/- 20 Pixel mit einbeziehen? Hast da noch ne Idee?

meinst du etwas in der Art?

Array.prototype.containsSimilarNumber = function(theNumber, maxDifference) {
	var min = theNumber - maxDifference;
	var max = theNumber + maxDifference;
	for(var i=0;i < this.length; i++) {
		if (this[i] >= min) 
			if (this[i] <= max)
				return true;
	}
	return false;
}

stars_upper = new Array;
for (j=0; j<18; j++) {
	var randNumber;
	do {
		randNumber = randRange(655,1564);
	} while (stars_upper.containsSimilarNumber(randNumber,20));
	stars_upper.push(randNumber);
}

(

[fabbsen]

ja sauber - um nicht zu sagen: perfekt...

11 beiträge und so'n Crack in Flashscripting

[hgseib]

http://www.seibsprogrammladen.de/fra...rithmen/Zufall
Zufallszahlen in sortierter Reihenfolge erzeugen

var max = 1600;
var min = 600;
var minabstand = 20;
var anzahl = 36;
var mm = max-min;
trace("theoretisch maximal möglich zahlen: "+int(mm/minabstand));
var t = getTimer();
//
Array.prototype.containsSimilarNumber = function(theNumber, maxDifference) {
  var min = theNumber-maxDifference;
  var max = theNumber+maxDifference;
  for (var i = 0; i<this.length; i++) {
    if (this[i]>=min) {
      if (this[i]<=max) return true;
  } }
  return false;
};
_ary = new Array();
for (j=0; j<anzahl; j++) {
  var randNumber;
  do {
    randNumber = int(min+Math.random()*mm);
  } while (_ary.containsSimilarNumber(randNumber, minabstand));
  _ary.push(randNumber);
}
//
trace(anzahl+" in "+(getTimer()-t)+" millisekunden");
_ary.sort(Array.NUMERIC);
trace(_ary.join("\n"));
trace("-prüfen-------");
for (j=1; j<anzahl; j++) trace(_ary[j]-_ary[j-1]);
//
//
trace("==========");
//
//
var ver = mm-anzahl*minabstand;
trace("es gib zusätzliche zu verteilen "+ver+" punkte");
var t = getTimer();
//
var _ary = [Math.random()];
for (var j = 1; j<=anzahl; j++) _ary.push(_ary[j-1]+Math.random());
ver /= _ary[anzahl];
_ary[0] = min+Math.round(ver*(_ary[1]-_ary[0]));
for (j=1; j<anzahl; j++) _ary[j] = _ary[j-1]+minabstand+Math.round(ver*(_ary[j+1]-_ary[j]));
_ary.pop();
//
trace(anzahl+" in "+(getTimer()-t)+" millisekunden");
trace(_ary.join('\n'));
trace("-prüfen-------");
for (j=1; j<anzahl; j++) trace(_ary[j]-_ary[j-1]);

[fabbsen]

ähm danke - aber das von DaisyW gefällt mir wesentlich besser:

1. schlank programmiert
2. erfüllt genau meine Anforderung

... trotzdem danke

[hgseib]

hier kann jeder machen was er will ;-)

will ja niemandes arbeit schlecht reden. das such-script endet in einer endlosschleife, wenn zu viele zahlen für den zahlenbereich verlangt werden und wenn es mal geht, dann ist die berechnungsdauer willkürlich lange. halt je nach zufallszahlen.

das hier ist (sorry) kürzer, geht immer und auch die berechnungsdauer ist viel kürzer und linear zur anzahl:

function randomAryMinMax(min, max, ab, anzahl) {
  var _ary = [Math.random()];
  for (var j = 1; j<=anzahl; j++) _ary.push(_ary[j-1]+Math.random());
  var ver = (max-min-anzahl*ab)/_ary[anzahl];
  _ary[0] = min+Math.round(ver*(_ary[1]-_ary[0]));
  for (j=1; j<anzahl; j++) _ary[j] = _ary[j-1]+ab+Math.round(ver*(_ary[j+1]-_ary[j]));
  _ary.pop();
  return _ary;
}
//
// Anwendungsbeispiel:
var max = 1600;
var min = 600;
var minabstand = 20;
var anzahl = 36;
var _ary = randomAryMinMax(min, max, minabstand, anzahl);
trace(_ary[0]);
for (j=1; j<anzahl; j++) trace(_ary[j]+" d="+(_ary[j]-_ary[j-1]));

[DaisyW]

Zitat von hgseib

will ja niemandes arbeit schlecht reden. [/code]

Hallo hgseib,

die Endlosschleife ergäbe sich, wenn man die Werte nicht kennt und die
Anzahl der gewünschten Zahlen für die Range zu groß ist. Das ist richtig. Ich habe aber auch nur einen Lösungsansatz zeigen wollen und nirgends gesagt, dass das ein 100%ig fertiges und narrensicheres Script ist. Ich kenne ja fabbsen's Vorgaben nicht - wenn er mit festen Werten arbeitet, dann tut's das so ...

Dein Script ist zugegebenermaßen schnell und kurz (und wunderbar unübersichtlich geschrieben) - aber es liefert nach meiner Ansicht leider auch keine wirklich echte Zufallsverteilung.

Schau dir einfach mal die Maximalwerte für den Abstand 'd' an. Ich habe mir den Spass gemacht und mal bei 5000 Durchläufen und fabbsen's Zahlen den Maximalwert für d ermittelt (bei meiner Lösung habe ich selbstverständlich sortiert ...) - da ergibt sich bei dir ein Maximalabstand d von ca. 125 - bei mir ca. 270. (rein rechnerisch, wenn auch sehr sehr unwahrscheinlich wäre ein Wert von ca. 500 möglich)

lg

Daisy

[hgseib]

will dich nicht angreifen, ist ja nett gemacht.
und hier geht es ja auch darum über unterschiedliche lösungen zu reden.


bei deiner lösung: wenn die zahlen zufällig sehr eng zusammen gesetzt werden, dann findet der algorithmus noch ein freies plätzchen. wenn die zahlen per zufall weiter auseinander liegen (also gleichmässiger verteilt), dann kann es vorkommen, das kein geeigneter zwischenraum mehr gefunden wird. man kann also nicht genau sagen, wieviel punkte gehen und ab wann es zu einer endlosschleife kommt.

wenn man es versteht ist mein algorithmus sehr übersichtlich ;-)
ich erstelle n zufallszahlen und skaliere die auf 0 bis 1.
dadurch ergeben deren differenzen (==abstände) zusammen einen wert <=1. (100%)
für n zahlen mit einem abstand von m wird mindestens n*m benötigt.
wenn man das von max-min abzieht, das ist die menge der punkte, die man verteilen kann.
und diese menge verteile ich gemäss der skalierten zufallszahlen. das ist der entscheidende unterschied!
ich gewährleiste, das der mindestabstand eingehalten wird, da ich den jeweils zum vorgängerwert addiere (ich muss nicht suchen). zusätzlich wird ein zufälliger wert aus dem pool der verteilbaren menge addiert.


zu deinen testversuchen:
nimm einfach das komplette script aus #6
ändere mal
var max = 1600;
in
var max = 16000;
und das mehrmals ausführen lassen.
also das müsste man statistisch auswerten, ob da tatsächlich keine normalverteilte zahlen dabei herauskommen. ich bezweifele das sehr. zumindestens optisch sehe ich bei beiden verfahren sowohl sehr grosse als auch sehr kleine abstände.

[DaisyW]

Zitat von hgseib

will dich nicht angreifen, ist ja nett gemacht.
und hier geht es ja auch darum über unterschiedliche lösungen zu reden.

Ich bin vollständig auf deiner Seite, wenn es darum geht, Lösungsansätze zu diskutieren. Nicht so ganz gefällt mir dein gönnerhafter Unterton und ein 'will ja niemandes arbeit schlecht reden' kann man sich doch auch verkneifen, wenn man es im folgenden Satz doch tut - aber vergessen wir's - ich bin alt genug und daher nicht so empfindlich ...

Zitat von hgseib

bei deiner lösung: wenn die zahlen zufällig sehr eng zusammen gesetzt werden, dann findet der algorithmus noch ein freies plätzchen. wenn die zahlen per zufall weiter auseinander liegen (also gleichmässiger verteilt), dann kann es vorkommen, das kein geeigneter zwischenraum mehr gefunden wird. man kann also nicht genau sagen, wieviel punkte gehen und ab wann es zu einer endlosschleife kommt.

ich denke, das kann man schon - du kannst doch einfach berechnen, wie groß die Range sein muss, dass es immer klappt, indem du den ungünstigsten Verteilungsfall betrachtest (bei anzahl Zahlen, einem Mindestabstand ab und einer Range von min bis max):
das erste Element sitzt dann auf der Position ab , jedes weitere beansprucht einen Raum von 2 x ab + 1. Es gilt also die Formel: max - min >= ab + (anzahl - 1) * ( 2 * ab +1). Wenn das gegeben ist (ist es bei sabbsen's Zahlen) - dann gibt es keine Endlosschleife - oder sehe ich da was falsch? Aber du hast insofern recht - für engere Ranges taugt der Algorithmus nicht.

Zitat von hgseib

wenn man es versteht ist mein algorithmus sehr übersichtlich ;-)
ich erstelle n zufallszahlen und skaliere die auf 0 bis 1.
dadurch ergeben deren differenzen (==abstände) zusammen einen wert <=1. (100%)
für n zahlen mit einem abstand von m wird mindestens n*m benötigt.
wenn man das von max-min abzieht, das ist die menge der punkte, die man verteilen kann.
und diese menge verteile ich gemäss der skalierten zufallszahlen. das ist der entscheidende unterschied!
ich gewährleiste, das der mindestabstand eingehalten wird, da ich den jeweils zum vorgängerwert addiere (ich muss nicht suchen). zusätzlich wird ein zufälliger wert aus dem pool der verteilbaren menge addiert.

ok - ich versuche, noch man auf einem anderen Weg zu zeigen, wo meines Erachtens nach ein Fehler steckt:

Du füllst ein Array der Größe anzahl mit einem Wert, zu dem du jedes mal einen random-Wert zwischen 0 und 1 addierst. Im Mittel inkrementierst du also jedes mal also mit 0.5 - hast also durchschnittlich einen Wert von (anzahl / 2) im letzen Array-Item (_ary[anzahl]). Der durch dein Array vorgegebene maximale Sprung zwischen zwei Werten ist aber nur 1. Also ist der maximale erreichbare Sprung im Endresultat (max - min) * 2 / anzahl. Im 'wirklichen Leben' sollte der aber bei (max - min - anzahl*(ab+1)) liegen - und das ist - abhängig von den Werten - recht deutlich größer. Du senkst also durch deine Methode die Wahrscheinlichkeit für Ausreisser in den Sprungabständen erheblich - deine Zahlen sind gleichmäßiger über das Feld verteilt, als es der 'reine Zufall' macht. Das war's was ich damit meinte, das das keine wirklich echte Zuallsverteilung ist, die dein Algorithus generiert. Aber es mag ja sein, dass es das auch für viele Anwendungen so tut ...

lg

Daisy

[hgseib]

das extremste ist, wenn anzahl der punkte mal mindestabstand genau so gross ist wie max- minus mindestbereich. also wenn die frei zu verteilende restmenge gleich null ist. dafür gibt es nur eine einzige lösung: alle punkte müssen exakt den mindestabstand einhalten.
wenn man einen punkt per zufall setzt ist es unwahrscheinlich, das der genau auf das raster kommt. in folge ist die aufgabe nicht mehr lösbar (endlosschleife) weil für die restlichen punkte kein genügend grosser freiraum mehr besteht.
(das programm müsste bereits gesetzte punkte verschieben um doch noch eine gültige lösung zu erhalten)

wenn eine restmenge besteht, dann ist dieses problem nicht 'schlagartig' gelöst, sondern je mehr zusätzlicher platz zur verfügung steht, desto wahrscheinlicher ist es, das es per zufall langt.
es kommt auf den zufall darauf an. also es ist nicht berechenbar, ab wieviel punkten es zu keiner endlosschleife kommen wird.

keine lösung gefunden, obwohl es zu diesen fällen gültige lösungen gibt, wenn man die punkte entsprechend verteilt. d.h. der zufall-test-algorithmus berücksichtigt nicht alle möglichen lösungen und kommt durch diese selektion zu einer grösseren standardverteilung(?). das zeigt aber auch, das durch die randbedingung, die punkte nicht vollkommen frei per zufall gesetzt werden können. die positionen der punkte beeinflussen sich gegenseitig (siehe verschieben um die lösung zu erhalten).


da die mindestabstände fix sind, kann man die aus der betrachtung ausklammern, indem man die punkte nur auf die restmenge verteilt und zum schluss überall die mindestabstände einschiebt.
bildlich betrachtet: wenn die restmenge gleich null ist, dann liegen alle punkte aufeinander. zieht man die restmenge in die länge, dann können sich die punkte immer 'wilder' auf dieser strecke verteilen.

aus dieser überlegung heraus habe ich nochmals vereinfacht:
[edit]ja ist klar, es gibt n-1 zwischenräume

[edit][edit]ja, ich ziehe diese funktion wieder zurück. hatte wohl zu viel auf die standardverteilung geachtet. damit bleibe ich bei meiner ersten version. und suche weiter, warum ich eine zu kleine standardverteilungen erhalte. obwohl es grundsätzlich richtig ist, das man die restmenge verteilen muss.

function randomAryMinMax(min, max, minabstand, anzahl) {
  var restmenge = max-min-(anzahl-1)*minabstand;
  var _ary = [];
  for (var i = 0; i<anzahl; i++) {
    _ary.push(int(Math.random()*restmenge+i*minabstand));
  }
  _ary.sort(Array.NUMERIC);
  return _ary;
}
trace(randomAryMinMax(600, 1600, 20, 30).join("\n"));

trace(randomAryMinMax(0, 100, 10, 11).join("\n"));
// -> 0,10,20,30,40,50,60,70,80,90,100

[DaisyW]

Zitat von hgseib

das extremste ist...

jaja weiss ich ja - und das hatte ich doch auch schon oben geschrieben - für alle Fälle, die unterhalb der beschriebenen Formel liegen, taugt mein Algorithmus nicht - und wenn es nur knapp drüber liegt, kann es unter Umständen auch etwas länger dauern, bis die Lösung gefunden wird. Wie du allerdings bei nach meiner Formel gültigen Werten zu einer Endlosschleife kommen willst ... da hätte ich gerne mal einen Beweis gesehen.

Zitat von hgseib

aus dieser überlegung heraus habe ich nochmals vereinfacht:
[edit]ja ist klar, es gibt n-1 zwischenräume ...

Ich dachte spontan: das ist brilliant - aber dann sah ich, dass das leider doch so nicht klappt. Probier's einfach noch mal aus - du wirst in fast allen Durchläufen Abstände finden, die < minabstand sind. Du siehst bestimmt auch gleich, wo der Denkfehler ist.
Schade - das war so schön gedacht ...

Grüße,

Daisy

[Janoscharlipp]

Also das letzte Script geht auf keinen Fall, hgseib.
Einfaches Beispiel für diese Zeile:

_ary.push(int(Math.random()*restmenge+i*minabstand));

restmenge = 10
minabstand = 2
Erste zwei Durchläufe:

1) i = 0; Math.random() = 0.2 => x = 2
2) i = 1; Math.random() = 0    => x = 2

restmenge einfach durch anzahl teilen darf man allerdings auch nicht, das würde die Verteilung kaputt machen.

Interessantes Problem!

[edding950]

Ich wäre ja dafür, dass Scriptsyntax auch entsprechend des Bereichs gehalten wird, indem gepostet wurde..

var temparr = [];
var arr = [];
var n = 18;
var rand = 655+random(1564-655);
 
while (n--)
{
    while (temparr[rand])
    {
        rand = 655+random(1564-655);
    }
    temparr[rand] = true;
    arr.push(rand);
}
 
trace(arr); 

Edit: Achso..bezüglich Mindestabstand, kann einfach die 'Auflösung' möglicher Werte geändert werden..also:

rand = 655+Math.round((random(20)*(1564-655)/20));