Matrix - Positionen - Zufall

Wissenschaft Physik
1

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

2

Dimension n, N Einsen:

zz:=0;

solange zz

Ciao Lutz
3 
> 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.
4

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)

5 
> 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** ;
6

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

7

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

8

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

9

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