How to resolve the algorithm Average loop length step by step in the J programming language

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Average loop length step by step in the J programming language

Table of Contents

Problem Statement

Let f be a uniformly-randomly chosen mapping from the numbers 1..N to the numbers 1..N (note: not necessarily a permutation of 1..N; the mapping could produce a number in more than one way or not at all). At some point, the sequence 1, f(1), f(f(1))... will contain a repetition, a number that occurring for the second time in the sequence.

Write a program or a script that estimates, for each N, the average length until the first such repetition. Also calculate this expected length using an analytical formula, and optionally compare the simulated result with the theoretical one.

This problem comes from the end of Donald Knuth's Christmas tree lecture 2011. Example of expected output:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Average loop length step by step in the J programming language

Source code in the j programming language

   (~.@, {&0 0@{:)^:_] 0
0
   (~.@, {&0 0@{:)^:_] 1
1 0


   0 0 ([: # (] ~.@, {:@] { [)^:_) 1
2


   (#.inv i.@^~)2
0 0
0 1
1 0
1 1


   (+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)1
1
   (+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)2
1.5
   (+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)3
1.88889
   (+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)4
2.21875
   (+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)5
2.5104
   (+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)6
2.77469


   ana=: +/@(!@[ % !@- * ^) 1+i.
   ana"0]1 2 3 4 5 6
1 1.5 1.88889 2.21875 2.5104 2.77469


   sim=: (+/ % #)@,@((]?@$~1e4,]) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)
   sim"0]1 2 3 4 5 6
1 1.5034 1.8825 2.22447 2.51298 2.76898


   (;:'N average analytic error'),:,.each(;ana"0 ([;];-|@%[) sim"0)1+i.20
+--+-------+--------+-----------+
|N |average|analytic|error      |
+--+-------+--------+-----------+
| 1|      1|      1 |          0|
| 2|    1.5|1.49955 |     0.0003|
| 3|1.88889| 1.8928 | 0.00207059|
| 4|2.21875|2.23082 | 0.00544225|
| 5| 2.5104|2.52146 | 0.00440567|
| 6|2.77469|2.78147 | 0.00244182|
| 7|3.01814| 3.0101 | 0.00266346|
| 8|3.24502|3.25931 | 0.00440506|
| 9|3.45832|3.45314 | 0.00149532|
|10|3.66022| 3.6708 | 0.00289172|
|11|3.85237|3.84139 | 0.00285049|
|12|4.03607|4.03252 |0.000881304|
|13|4.21235|4.18358 | 0.00682833|
|14|4.38203|4.38791 | 0.00134132|
|15|4.54581|4.54443 |0.000302246|
|16|4.70426|4.71351 | 0.00196721|
|17|4.85787|4.85838 |0.000104089|
|18|5.00706|5.00889 |0.000365752|
|19| 5.1522|5.14785 |0.000843052|
|20|5.29358|5.28587 | 0.00145829|
+--+-------+--------+-----------+

You may also check:How to resolve the algorithm Abbreviations, simple step by step in the C programming language
You may also check:How to resolve the algorithm Time a function step by step in the Factor programming language
You may also check:How to resolve the algorithm Polymorphism step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Generate lower case ASCII alphabet step by step in the 6502 Assembly programming language
You may also check:How to resolve the algorithm Program name step by step in the Joy programming language