Your algorithm keeps adding random integers to a list until an element repeats. At that point it stops.
Here's your implementation wrapped up into a function:
fun1[n_] :=
Module[{z = {}, w},
While[Not@MemberQ[z, w = RandomInteger[n]],
AppendTo[z, w]
];
z
]
Here's the same, but using associations. This avoids the quadratic complexity that is caused by MemberQ
and AppendTo
.
fun4[n_] :=
Module[{asc = <||>, k},
While[Not@KeyMemberQ[asc, k = RandomInteger[n]],
asc[k] = 0;
];
Keys[asc]
]
Benchmarking:
timings[fun_] :=
Table[
{n, First@AbsoluteTiming@Do[fun[n], {5000}]},
{n, 2^Range[6, 16]}
]
ListLogLogPlot[timings /@ {fun1, fun4}, PlotLegends -> {fun1, fun4},
AxesLabel -> {"n", "timing"}]

Above around $n \approx 1000$, the association method becomes faster.
I have idea to use NestWhileList or Reap/Sow, but can't guess how to сheck condition "value already was added in array".
I believe that a Nest
-like implementation will be slower because it will force creating a full copy of the association at every step instead of changing it efficiently in-place (as asc[k] = 0
does in the code above). This will make the complexity of the algorithm worse again (just as AppendTo
does in fun1
by forcing a full copy of z
).
To overcome to difficulty with sharing a value between the iterating function and the test function in NestWhile
, we can use a tail-recursive implementation:
Clear[fun5, fun5i]
fun5i[n_, asc_] :=
With[{k = RandomInteger[n]},
If[KeyMemberQ[asc, k], Keys[asc], fun5i[n, <|asc, k -> 0|>]]
]
fun5[n_] := fun5i[n, <||>]
This does essentially the same thing as fun4
, but it is much slower due to copying the association at each step.
RandomSample[]
. $\endgroup$Keys@FixedPoint[ <|#, RandomInteger[n] -> 0|> &, <||> ]
$\endgroup$RandomInteger
only as an example. I have other more complex function $\endgroup$===
(implicitly inFixedPoint
) as a stopping condition. The comparison is too slow. $\endgroup$