Ich möchte eine mit Nullen gefüllte Matrix mit N
einsen füllen. Das Positionsbild der N einsen soll „zufällig“ sein.
Ein Zufallsgenerator liefert eine Zahl, die auf eins normiert ist.
Hat jemand eine Idee für eine Lösung des Problems?
Danke
Ich möchte eine mit Nullen gefüllte Matrix mit N
einsen füllen. Das Positionsbild der N einsen soll „zufällig“ sein.
Ein Zufallsgenerator liefert eine Zahl, die auf eins normiert ist.
Hat jemand eine Idee für eine Lösung des Problems?
Danke
Diese Frage stammt aus dem Jahr 2001. Weißt du es heute besser?
Aktuelle Antwort ergänzenDimension n, N Einsen:
zz:=0;
solange zz
Ciao Lutz
Antwort auf Lutz_Lehmannzum Beitrag ↑Dimension n, N Einsen: zz:=0; solange zz Ciao Lutz
> zz:=0;
>
> solange zz
Das hat aber den Nachteil, daß der Zeitaufwand quadratisch mit der Größe der Matrix steigt, weil die Wahrscheinlichkeit, daß zufällig eine freie Gittperposition gefunden wird zum Ende der Schleife immer weiter abnimmt.
Die Alternative besteht in der Definition einer verketteten Liste, die nur freie Gitterpositionen ethält und aus der alle bereits besetzen Positionen entfernt werden. In Delphi sieht das so aus:
**const**
m = 10 ;
n = 10 ;
**type**
PInteger = ^Integer ;
TMatrix = array[1..m,1..n] of Integer ;
**procedure** FillMatrix( **var** Matrix:TMatrix;Anzahl:Integer) ;
**var**
i,j: Integer ;
FreePosition: TList ;
**begin**
FreePosition:=TList.Create ;
**for** i:=1 **to** m **do** **for** j:=1 **to** n **do** if Matrix[i,j]=0 then FreePosition.Add(@Matrix[i,j]) ;
i:=0 ;
**while** (iand (FreePosition.Count\>0) **do** **begin**
j:=random(FreePosition.Count) ;
PInteger(FreePosition.Items[j])^:=1 ;
FreePosition.Delete(j) ; inc(i) ;
**end** ;
FreePosition.Destroy ;
**end** ;
Nach dieser Methode steigt der Zeitaufwand linear mit der Größe der Matrix.
Antwort auf DrStupidzum Beitrag ↑> zz:=0; > > solange zz Das hat aber den Nachteil, daß der Zeitaufwand quadratisch mit der Größe der Matrix steigt, weil die Wahrscheinlichkeit, daß zufällig eine freie Gittperposition gefunden wird zum Ende der Schleife …
Das hat aber den Nachteil, daß der Zeitaufwand quadratisch mit
der Größe der Matrix steigt, weil die Wahrscheinlichkeit, daß
zufällig eine freie Gittperposition gefunden wird zum Ende der
Schleife immer weiter abnimmt.
Ok,ok,
abgesehen vom Aufwand der Listenverwaltung,…
der Fragende meint hoffentlich duenn besetzte Matrizen. D.h. die Wk, auf eine 1 zu treffen, ist kleiner N/n^2=O(1/n). Damit wird der Erwartungswert fuer Neuversuche ueber die gesamte Rechnung ebenfalls O(1/n). Geht also doch ganz gut.
Bei grossen duenn besetzten Matrizen waer die geeignete Datenstruktur wichtiger als solche Randeffekte.
Ciao Lutz
PS Summe k p^k= p/(1-p)^2=O(N/n^2)
Antwort auf DrStupidzum Beitrag ↑> zz:=0; > > solange zz Das hat aber den Nachteil, daß der Zeitaufwand quadratisch mit der Größe der Matrix steigt, weil die Wahrscheinlichkeit, daß zufällig eine freie Gittperposition gefunden wird zum Ende der Schleife …
> zz:=0;
>
> solange zz
Da fällt mir gerade eine Möglichkeit ein, diese Routine für große N zu beschleunigen:
**if** Anzahlthen **begin**
**for** i:=1 **to** m **do** **for** j:=1 **to** n **do** Matrix[i,j]:=1 ;
z:=m\*n-Anzahl ; e:=1 ;
**end** **else** **begin**
z:=Anzahl ; e:=0 ;
**end** ;
zz:=0 ;
**while** zzdo **begin**
i:=1+Random(m);
j:=1+Random(n);
**if** Matrix[i,j]=e **then** **begin**
Matrix[i,j]:=1-e ; inc(zz) ;
**end** ;
**end** ;
Aehm … geht das nicht viel einfacher ??
Also:
k=Anzahl der Zeilen
m=Anzahl der Spalten
Matrix[0…k-1, 0…m-1] ist die Matrix
rnd() liefert eine Fliesskommazahl im Intervall [0.0,1.0[
for (int i=0; i
Antwort auf Gastzum Beitrag ↑Aehm … geht das nicht viel einfacher ?? Also: k=Anzahl der Zeilen m=Anzahl der Spalten Matrix[0…k-1, 0…m-1] ist die Matrix rnd() liefert eine Fliesskommazahl im Intervall [0.0,1.0[ for (int i=0; i
Hi!
Aehm … geht das nicht viel einfacher ??
Nein. Wenn Du am Schluß genau N Einsen in der Matrix drinhaben willst, mußt Du sicherstellen, daß Du nur dort eine Eins hinsetzt, wo noch eine Null steht. Du mußt also die „Mehrfachbesetzung“ von Feldern mit Einsen verhindern (der Zufallsgenerator weiß ja nicht, wo schon eine Eins steht).
Mit freundlichem Gruß
Martin
Antwort auf Martinzum Beitrag ↑Hi! Aehm … geht das nicht viel einfacher ?? Nein. Wenn Du am Schluß genau N Einsen in der Matrix drinhaben willst, mußt Du sicherstellen, daß Du nur dort eine Eins hinsetzt, wo noch eine Null steht. Du mußt also die „Meh …
Ahja, es sollen wirklich genau N Einsen sein. Wie gross ist den die Matrix ? Wenn die Anzahl der Positionen deutlich hoeher ist, dann ist doch die Loesung von Lutz Lehmann praktisch und gut.
Gruss, Moriarty
Antwort auf DrStupidzum Beitrag ↑> zz:=0; > > solange zz Das hat aber den Nachteil, daß der Zeitaufwand quadratisch mit der Größe der Matrix steigt, weil die Wahrscheinlichkeit, daß zufällig eine freie Gittperposition gefunden wird zum Ende der Schleife …
Zu Lutz und MrStupid
Das mit der verketteten Liste ist eine gute Idee. Ich habe mich nämlich schon gefragt, was passiert wenn nicht mehr viele Gitterpositionen zur Verfügung stehen.
Diese ist damit ja schon beantwortet.
Ich werde ausprobieren, ob ich mit der ‚Lutz-Methode‘ hinkomme; allerdings finde ich die ‚MrStupid-Methode‘ „sicherer“!
Schaun w’ mal!
Danke an euch beide!
M.f.G
H. Biegler
Deine Antwort
Zum Antworten bitte anmelden oder kostenlos registrieren.