Percolation/Mean cluster density: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: syntax coloured) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 25: | Line 25: | ||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="11l">UInt32 seed = 0 |
||
F nonrandom() |
F nonrandom() |
||
:seed = 1664525 * :seed + 1013904223 |
:seed = 1664525 * :seed + 1013904223 |
||
Line 81: | Line 81: | ||
sum += clusterDensity(n, pp) |
sum += clusterDensity(n, pp) |
||
V sim = sum / tt |
V sim = sum / tt |
||
print(‘t = #. p = #.2 n = #4 sim = #.5’.format(tt, pp, n, sim))</ |
print(‘t = #. p = #.2 n = #4 sim = #.5’.format(tt, pp, n, sim))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 111: | Line 111: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 187: | Line 187: | ||
free(map); |
free(map); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 219: | Line 219: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|python}} |
{{trans|python}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.random, std.math, std.array, |
||
std.range, std.ascii; |
std.range, std.ascii; |
||
Line 308: | Line 308: | ||
nIters, prob, side, density); |
nIters, prob, side, density); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Found 26 clusters in this 15 by 15 grid: |
<pre>Found 26 clusters in this 15 by 15 grid: |
||
Line 340: | Line 340: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
We use the canvas bit-map as 2D-matrix. For extra-extra credit, a 800x800 nice cluster tapestry image is shown here : http://www.echolalie.org/echolisp/images/rosetta-clusters-800.png. |
We use the canvas bit-map as 2D-matrix. For extra-extra credit, a 800x800 nice cluster tapestry image is shown here : http://www.echolalie.org/echolisp/images/rosetta-clusters-800.png. |
||
< |
<syntaxhighlight lang="scheme"> |
||
(define-constant BLACK (rgb 0 0 0.6)) |
(define-constant BLACK (rgb 0 0 0.6)) |
||
(define-constant WHITE -1) |
(define-constant WHITE -1) |
||
Line 378: | Line 378: | ||
(writeln 'n n 'Cn Cn 'density (// Cn (* n n) 5) ) |
(writeln 'n n 'Cn Cn 'density (// Cn (* n n) 5) ) |
||
(vector->pixels C)) ;; to screen |
(vector->pixels C)) ;; to screen |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 389: | Line 389: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: combinators formatting generalizations kernel math |
||
math.matrices random sequences ; |
math.matrices random sequences ; |
||
IN: rosetta-code.mean-cluster-density |
IN: rosetta-code.mean-cluster-density |
||
Line 430: | Line 430: | ||
] each ; |
] each ; |
||
MAIN: main</ |
MAIN: main</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 442: | Line 442: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 539: | Line 539: | ||
fmt.Printf("t=%3d p=%4.2f n=%5d sim=%7.5f\n", t, p, n, sim) |
fmt.Printf("t=%3d p=%4.2f n=%5d sim=%7.5f\n", t, p, n, sim) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 569: | Line 569: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">{-# language FlexibleContexts #-} |
||
import Data.List |
import Data.List |
||
import Data.Maybe |
import Data.Maybe |
||
Line 631: | Line 631: | ||
main = newStdGen >>= mapM_ (uncurry (printf "%d\t%.5f\n")) . res |
main = newStdGen >>= mapM_ (uncurry (printf "%d\t%.5f\n")) . res |
||
where |
where |
||
res = mapM task [10,50,100,500]</ |
res = mapM task [10,50,100,500]</syntaxhighlight> |
||
<pre>λ> newStdGen >>= putStrLn . showClusters . randomMatrix 15 |
<pre>λ> newStdGen >>= putStrLn . showClusters . randomMatrix 15 |
||
Line 666: | Line 666: | ||
Once we have this, we can identify clusters by propagating information in a single direction through the matrix using this operation, rotating the matrix 90 degrees, and then repeating this combination of operations four times. And, finally, by keeping at this until there's nothing more to be done. |
Once we have this, we can identify clusters by propagating information in a single direction through the matrix using this operation, rotating the matrix 90 degrees, and then repeating this combination of operations four times. And, finally, by keeping at this until there's nothing more to be done. |
||
< |
<syntaxhighlight lang="j">congeal=: |.@|:@((*@[*>.)/\.)^:4^:_</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang="j"> M=:0.4>?6 6$0 |
||
M |
M |
||
1 0 0 0 0 0 |
1 0 0 0 0 0 |
||
Line 691: | Line 691: | ||
71 71 0 0 0 0 |
71 71 0 0 0 0 |
||
0 0 0 149 0 113 |
0 0 0 149 0 113 |
||
131 131 0 149 149 0</ |
131 131 0 149 149 0</syntaxhighlight> |
||
We did not have to use primes there - any mechanism for assigning distinct positive integers to the 1s would work. And, in fact, it might be nice if - once we found our clusters - we assigned the smallest distinct positive integers to the clusters. This would allow us to use simple indexing to map the array to characters. |
We did not have to use primes there - any mechanism for assigning distinct positive integers to the 1s would work. And, in fact, it might be nice if - once we found our clusters - we assigned the smallest distinct positive integers to the clusters. This would allow us to use simple indexing to map the array to characters. |
||
< |
<syntaxhighlight lang="j">idclust=: $ $ [: (~. i.])&.(0&,)@,@congeal ] * 1 + i.@$</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> idclust M |
||
1 0 0 0 0 0 |
1 0 0 0 0 0 |
||
0 0 0 2 0 0 |
0 0 0 2 0 0 |
||
Line 712: | Line 712: | ||
CC.... |
CC.... |
||
...D.E |
...D.E |
||
FF.DD.</ |
FF.DD.</syntaxhighlight> |
||
Now we just need a measure of cluster density. Formally cluster density seems to be defined as the number of clusters divided by the total number of elements of the matrix. Thus: |
Now we just need a measure of cluster density. Formally cluster density seems to be defined as the number of clusters divided by the total number of elements of the matrix. Thus: |
||
< |
<syntaxhighlight lang="j">K=: (%&#~ }.@~.)&,</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> K idclust M |
||
0.1666667</ |
0.1666667</syntaxhighlight> |
||
So we can create a word that performs a simulation experiment, given a probability getting a 1 and the number of rows (and columns) of our square matrix M. |
So we can create a word that performs a simulation experiment, given a probability getting a 1 and the number of rows (and columns) of our square matrix M. |
||
< |
<syntaxhighlight lang="j">experiment=: K@ idclust@: > 0 ?@$~ ,~</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> 0.4 experiment 6 |
||
0.1666667 |
0.1666667 |
||
0.4 experiment 6 |
0.4 experiment 6 |
||
0.1944444</ |
0.1944444</syntaxhighlight> |
||
The task wants us to perform at least five trials for sizes up to 1000 by 1000 with probability of 1 being 0.5: |
The task wants us to perform at least five trials for sizes up to 1000 by 1000 with probability of 1 being 0.5: |
||
< |
<syntaxhighlight lang="j">trials=: 0.5&experiment"0@#</syntaxhighlight> |
||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> 6 trials 3 |
||
0.1111111 0.1111111 0.2222222 0.1111111 0.1111111 0.3333333 |
0.1111111 0.1111111 0.2222222 0.1111111 0.1111111 0.3333333 |
||
6 trials 10 |
6 trials 10 |
||
Line 751: | Line 751: | ||
0.06563333 0.06663333 0.06713333 0.06727778 0.06658889 0.06664444 |
0.06563333 0.06663333 0.06713333 0.06727778 0.06658889 0.06664444 |
||
6 trials 1000 |
6 trials 1000 |
||
0.066079 0.066492 0.065847 0.065943 0.066318 0.065998</ |
0.066079 0.066492 0.065847 0.065943 0.066318 0.065998</syntaxhighlight> |
||
Now for averages (these are different trials from the above): |
Now for averages (these are different trials from the above): |
||
< |
<syntaxhighlight lang="j">mean=: +/%# |
||
mean 8 trials 3 |
mean 8 trials 3 |
||
0.1805556 |
0.1805556 |
||
Line 767: | Line 767: | ||
0.06749861 |
0.06749861 |
||
mean 8 trials 1000 |
mean 8 trials 1000 |
||
0.06616738</ |
0.06616738</syntaxhighlight> |
||
Finally, for the extra credit (thru taken from the [[Loops/Downward_for#J|Loops/Downward for]] task): |
Finally, for the extra credit (thru taken from the [[Loops/Downward_for#J|Loops/Downward for]] task): |
||
< |
<syntaxhighlight lang="j">thru=: <./ + i.@(+*)@-~</syntaxhighlight> |
||
< |
<syntaxhighlight lang="j"> (idclust 0.5 > 0 ?@$~ 15 15) {'.', 'A' thru&.(a.&i.) 'Z' |
||
A.......B..C... |
A.......B..C... |
||
AAAA...D..E.F.. |
AAAA...D..E.F.. |
||
Line 788: | Line 788: | ||
..AA..A.A...AAA |
..AA..A.A...AAA |
||
.M.A.AA.AA..AA. |
.M.A.AA.AA..AA. |
||
.MM..A.N..O..A.</ |
.MM..A.N..O..A.</syntaxhighlight> |
||
'''Collected definitions''' |
'''Collected definitions''' |
||
< |
<syntaxhighlight lang="j">congeal=: |.@|:@((*@[*>.)/\.)^:4^:_ |
||
idclust=: $ $ [: (~. i.])&.(0&,)@,@congeal ] * 1 + i.@$ |
idclust=: $ $ [: (~. i.])&.(0&,)@,@congeal ] * 1 + i.@$ |
||
Line 802: | Line 802: | ||
mean=:+/ % # |
mean=:+/ % # |
||
thru=: <./ + i.@(+*)@-~</ |
thru=: <./ + i.@(+*)@-~</syntaxhighlight> |
||
'''Extra Credit''' |
'''Extra Credit''' |
||
< |
<syntaxhighlight lang="j"> M=: (* 1+i.@$)?15 15$2 |
||
M |
M |
||
0 2 3 4 0 6 0 8 0 10 11 12 0 0 15 |
0 2 3 4 0 6 0 8 0 10 11 12 0 0 15 |
||
Line 854: | Line 854: | ||
16 16 16 0 0 17 0 15 15 15 15 15 0 15 15 |
16 16 16 0 0 17 0 15 15 15 15 15 0 15 15 |
||
16 16 16 0 17 17 17 0 0 15 0 15 0 0 0 |
16 16 16 0 17 17 17 0 0 15 0 15 0 0 0 |
||
16 16 16 0 0 0 17 17 0 15 15 0 0 18 0</ |
16 16 16 0 0 0 17 17 0 15 15 0 0 18 0</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">using Printf, Distributions |
||
newgrid(p::Float64, r::Int, c::Int=r) = rand(Bernoulli(p), r, c) |
newgrid(p::Float64, r::Int, c::Int=r) = rand(Bernoulli(p), r, c) |
||
Line 909: | Line 909: | ||
sim = mean(clusterdensity(p, n) for _ in 1:nrep) |
sim = mean(clusterdensity(p, n) for _ in 1:nrep) |
||
@printf("nrep = %2i p = %.2f dim = %-13s sim = %.5f\n", nrep, p, "$n × $n", sim) |
@printf("nrep = %2i p = %.2f dim = %-13s sim = %.5f\n", nrep, p, "$n × $n", sim) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 938: | Line 938: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="scala">// version 1.2.10 |
||
import java.util.Random |
import java.util.Random |
||
Line 1,017: | Line 1,017: | ||
w = w shl 1 |
w = w shl 1 |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Sample output: |
Sample output: |
||
Line 1,055: | Line 1,055: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">(*Calculate C_n / n^2 for n=1000, 2000, ..., 10 000*) |
||
In[1]:= Table[N[Max@MorphologicalComponents[ |
In[1]:= Table[N[Max@MorphologicalComponents[ |
||
RandomVariate[BernoulliDistribution[.5], {n, n}], |
RandomVariate[BernoulliDistribution[.5], {n, n}], |
||
Line 1,064: | Line 1,064: | ||
(*Show a 15x15 matrix with each cluster given an incrementally higher number, Colorize instead of MatrixForm creates an image*) |
(*Show a 15x15 matrix with each cluster given an incrementally higher number, Colorize instead of MatrixForm creates an image*) |
||
In[3]:= MorphologicalComponents[RandomChoice[{0, 1}, {15, 15}], CornerNeighbors -> False] // MatrixForm</ |
In[3]:= MorphologicalComponents[RandomChoice[{0, 1}, {15, 15}], CornerNeighbors -> False] // MatrixForm</syntaxhighlight> |
||
Line 1,088: | Line 1,088: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="nim">import random, sequtils, strformat |
||
const |
const |
||
Line 1,157: | Line 1,157: | ||
sum += clusterDensity(n, P) |
sum += clusterDensity(n, P) |
||
let sim = sum / T |
let sim = sum / T |
||
echo &"t = {T} p = {P:4.2f} n = {n:4} sim = {sim:7.5f}"</ |
echo &"t = {T} p = {P:4.2f} n = {n:4} sim = {sim:7.5f}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,186: | Line 1,186: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">$fill = 'x'; |
||
$D{$_} = $i++ for qw<DeadEnd Up Right Down Left>; |
$D{$_} = $i++ for qw<DeadEnd Up Right Down Left>; |
||
Line 1,257: | Line 1,257: | ||
$total += perctest($N) for 1..$trials; |
$total += perctest($N) for 1..$trials; |
||
printf "𝘱 = 0.5, trials = $trials, 𝘕 = %4d, 𝘒 = %.4f\n", $N, $total / $trials; |
printf "𝘱 = 0.5, trials = $trials, 𝘕 = %4d, 𝘒 = %.4f\n", $N, $total / $trials; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 1 1 . . . . 2 2 2 . . . . . |
<pre> 1 1 1 . . . . 2 2 2 . . . . . |
||
Line 1,284: | Line 1,284: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|C}} |
{{trans|C}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> |
||
Line 1,352: | Line 1,352: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,382: | Line 1,382: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from __future__ import division |
||
from random import random |
from random import random |
||
import string |
import string |
||
Line 1,444: | Line 1,444: | ||
sim = fsum(cluster_density(n, p) for i in range(t)) / t |
sim = fsum(cluster_density(n, p) for i in range(t)) / t |
||
print('t=%3i p=%4.2f n=%5i sim=%7.5f' |
print('t=%3i p=%4.2f n=%5i sim=%7.5f' |
||
% (t, p, n, sim))</ |
% (t, p, n, sim))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,473: | Line 1,473: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(require srfi/14) ; character sets |
(require srfi/14) ; character sets |
||
Line 1,569: | Line 1,569: | ||
(define grd (build-random-grid 1/2 1000 1000)) |
(define grd (build-random-grid 1/2 1000 1000)) |
||
(/ (for/sum ((g (in-fxvector grd)) #:when (zero? g)) 1) (fxvector-length grd)) |
(/ (for/sum ((g (in-fxvector grd)) #:when (zero? g)) 1) (fxvector-length grd)) |
||
(display-sample-clustering 1/2))</ |
(display-sample-clustering 1/2))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,607: | Line 1,607: | ||
{{works with|Rakudo|2017.02}} |
{{works with|Rakudo|2017.02}} |
||
<lang |
<syntaxhighlight lang="raku" line>my @perc; |
||
my $fill = 'x'; |
my $fill = 'x'; |
||
Line 1,673: | Line 1,673: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>. . 1 . 2 . . 3 . . . 4 . . . |
<pre>. . 1 . 2 . . 3 . . . 4 . . . |
||
Line 1,702: | Line 1,702: | ||
Note that the queue (variables <code>q</code> and <code>k</code>) used to remember where to find cells when flood-filling the cluster is maintained as a list ''segment''; the front of the list is not trimmed for performance reasons. (This would matter with very long queues, in which case the queue could be shortened occasionally; ''frequent'' trimming is still slower though, because Tcl backs its “list” datatype with arrays and not linked lists.) |
Note that the queue (variables <code>q</code> and <code>k</code>) used to remember where to find cells when flood-filling the cluster is maintained as a list ''segment''; the front of the list is not trimmed for performance reasons. (This would matter with very long queues, in which case the queue could be shortened occasionally; ''frequent'' trimming is still slower though, because Tcl backs its “list” datatype with arrays and not linked lists.) |
||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6 |
||
proc determineClusters {w h p} { |
proc determineClusters {w h p} { |
||
Line 1,756: | Line 1,756: | ||
} |
} |
||
puts "n=$n, K(p)=[expr {$tot/5.0/$n**2}]" |
puts "n=$n, K(p)=[expr {$tot/5.0/$n**2}]" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,788: | Line 1,788: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "random" for Random |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 1,869: | Line 1,869: | ||
Fmt.print("$5d $9.6f", w, t) |
Fmt.print("$5d $9.6f", w, t) |
||
w = w << 1 |
w = w << 1 |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,908: | Line 1,908: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="zkl">const X=-1; // the sentinal that marks an untouched cell |
||
var C,N,NN,P; |
var C,N,NN,P; |
||
fcn createC(n,p){ |
fcn createC(n,p){ |
||
Line 1,936: | Line 1,936: | ||
foreach z in (n){ createC(N,p); k+=countClusters().toFloat()/NN; } |
foreach z in (n){ createC(N,p); k+=countClusters().toFloat()/NN; } |
||
k/n |
k/n |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">createC(15,0.5); |
||
println("width=%d, p=%.1f, %d clusters:".fmt(N,P,countClusters())); |
println("width=%d, p=%.1f, %d clusters:".fmt(N,P,countClusters())); |
||
showCluster(); |
showCluster(); |
||
println("p=0.5, 5 iterations:"); |
println("p=0.5, 5 iterations:"); |
||
w:=4; do(6){ println("%5d %9.6f".fmt(w,tests(w, 5, 0.5))); w*=4; }</ |
w:=4; do(6){ println("%5d %9.6f".fmt(w,tests(w, 5, 0.5))); w*=4; }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |