#37636

Committed 30 Sep 2023 06:44AM UTC coverage: 86.537% (-0.9%) from 87.418%

Build # #37636

Build Type

push

local

Committed by

web-flow

Commit Message

[REPLCompletions] suppress false positive field completions (#51502)

Field completions can be wrong when `getproperty` and `propertynames`
are overloaded for a target object type, since a custom `getproperty`
does not necessarily accept field names. This commit simply suppresses
field completions in such cases. Fixes the second part of #51499.

Run Details

15 of 15 new or added lines in 1 file covered. (100.0%)

73123 of 84499 relevant lines covered (86.54%)

12113738.76 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.88

/stdlib/Random/src/misc.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

## rand!(::BitArray) && bitrand

function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})
    isempty(B) && return B
    Bc = B.chunks
    rand!(rng, Bc)
    Bc[end] &= Base._msk_end(B)
    return B
end

"""
    bitrand([rng=default_rng()], [dims...])

Generate a `BitArray` of random boolean values.

# Examples
```jldoctest
julia> bitrand(Xoshiro(123), 10)
10-element BitVector:
 0
 1
 0
 1
 0
 1
 0
 0
 1
 1
```
"""
bitrand(r::AbstractRNG, dims::Dims)   = rand!(r, BitArray(undef, dims))
bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))

bitrand(dims::Dims)   = rand!(BitArray(undef, dims))
bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))


## randstring (often useful for temporary filenames/dirnames)

"""
    randstring([rng=default_rng()], [chars], [len=8])

Create a random string of length `len`, consisting of characters from
`chars`, which defaults to the set of upper- and lower-case letters
and the digits 0-9. The optional `rng` argument specifies a random
number generator, see [Random Numbers](@ref).

# Examples
```jldoctest
julia> Random.seed!(3); randstring()
"Lxz5hUwn"

julia> randstring(Xoshiro(3), 'a':'z', 6)
"iyzcsm"

julia> randstring("ACGT")
"TGCTCCTC"
```

!!! note
    `chars` can be any collection of characters, of type `Char` or
    `UInt8` (more efficient), provided [`rand`](@ref) can randomly
    pick characters from it.
"""
function randstring end

let b = UInt8['0':'9';'A':'Z';'a':'z']
    global randstring

    function randstring(r::AbstractRNG, chars=b, n::Integer=8)
        T = eltype(chars)
        if T === UInt8
            str = Base._string_n(n)
            GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)
            return str
        else
            v = Vector{T}(undef, n)
            rand!(r, v, chars)
            return String(v)
        end
    end

    randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)
    randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)
    randstring(n::Integer) = randstring(default_rng(), b, n)
end


## randsubseq & randsubseq!

# Fill S (resized as needed) with a random subsequence of A, where
# each element of A is included in S with independent probability p.
# (Note that this is different from the problem of finding a random
#  size-m subset of A where m is fixed!)
function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)
    require_one_based_indexing(S, A)
    0 <= p <= 1 || throw(ArgumentError("probability $p not in [0,1]"))
    n = length(A)
    p == 1 && return copyto!(resize!(S, n), A)
    empty!(S)
    p == 0 && return S
    nexpected = p * length(A)
    sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))
    if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better
        for i = 1:n
            rand(r) <= p && push!(S, A[i])
        end
    else
        # Skip through A, in order, from each element i to the next element i+s
        # included in S. The probability that the next included element is
        # s==k (k > 0) is (1-p)^(k-1) * p, and hence the probability (CDF) that
        # s is in {1,...,k} is 1-(1-p)^k = F(k).   Thus, we can draw the skip s
        # from this probability distribution via the discrete inverse-transform
        # method: s = ceil(F^{-1}(u)) where u = rand(), which is simply
        # s = ceil(log(rand()) / log1p(-p)).
        # -log(rand()) is an exponential variate, so can use randexp().
        L = -1 / log1p(-p) # L > 0
        i = 0
        while true
            s = randexp(r) * L
            s >= n - i && return S # compare before ceil to avoid overflow
            push!(S, A[i += ceil(Int,s)])
        end
        # [This algorithm is similar in spirit to, but much simpler than,
        #  the one by Vitter for a related problem in "Faster methods for
        #  random sampling," Comm. ACM Magazine 7, 703-718 (1984).]
    end
    return S
end

"""
    randsubseq!([rng=default_rng(),] S, A, p)

Like [`randsubseq`](@ref), but the results are stored in `S`
(which is resized as needed).

# Examples
```jldoctest
julia> S = Int64[];

julia> randsubseq!(Xoshiro(123), S, 1:8, 0.3)
2-element Vector{Int64}:
 4
 7

julia> S
2-element Vector{Int64}:
 4
 7
```
"""
randsubseq!(S::AbstractArray, A::AbstractArray, p::Real) = randsubseq!(default_rng(), S, A, p)

randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =
    randsubseq!(r, T[], A, p)

"""
    randsubseq([rng=default_rng(),] A, p) -> Vector

Return a vector consisting of a random subsequence of the given array `A`, where each
element of `A` is included (in order) with independent probability `p`. (Complexity is
linear in `p*length(A)`, so this function is efficient even if `p` is small and `A` is
large.) Technically, this process is known as "Bernoulli sampling" of `A`.

# Examples
```jldoctest
julia> randsubseq(Xoshiro(123), 1:8, 0.3)
2-element Vector{Int64}:
 4
 7
```
"""
randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)


## rand Less Than Masked 52 bits (helper function)

"Return a sampler generating a random `Int` (masked with `mask`) in ``[0, n)``, when `n <= 2^52`."
ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))

## shuffle & shuffle!

"""
    shuffle!([rng=default_rng(),] v::AbstractArray)

In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
optionally supplying the random-number generator `rng`.

# Examples
```jldoctest
julia> shuffle!(Xoshiro(123), Vector(1:10))
10-element Vector{Int64}:
  5
  4
  2
  3
  6
 10
  8
  1
  9
  7
```
"""
function shuffle!(r::AbstractRNG, a::AbstractArray)
    # keep it consistent with `randperm!` and `randcycle!` if possible
    require_one_based_indexing(a)
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    mask = 3
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i, mask))
        a[i], a[j] = a[j], a[i]
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)

"""
    shuffle([rng=default_rng(),] v::AbstractArray)

Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
number generator (see [Random Numbers](@ref)).
To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
indices, see [`randperm`](@ref).

# Examples
```jldoctest
julia> shuffle(Xoshiro(123), Vector(1:10))
10-element Vector{Int64}:
  5
  4
  2
  3
  6
 10
  8
  1
  9
  7
```
"""
shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))
shuffle(a::AbstractArray) = shuffle(default_rng(), a)

shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))

## randperm & randperm!

"""
    randperm([rng=default_rng(),] n::Integer)

Construct a random permutation of length `n`. The optional `rng`
argument specifies a random number generator (see [Random
Numbers](@ref)). The element type of the result is the same as the type
of `n`.

To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
[`shuffle!`](@ref).

!!! compat "Julia 1.1"
    In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
    while in Julia 1.0 `eltype(v) == Int`.

# Examples
```jldoctest
julia> randperm(Xoshiro(123), 4)
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))
randperm(n::Integer) = randperm(default_rng(), n)

"""
    randperm!([rng=default_rng(),] A::Array{<:Integer})

Construct in `A` a random permutation of length `length(A)`. The
optional `rng` argument specifies a random number generator (see
[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
[`shuffle`](@ref) or [`shuffle!`](@ref).

# Examples
```jldoctest
julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
function randperm!(r::AbstractRNG, a::Array{<:Integer})
    # keep it consistent with `shuffle!` and `randcycle!` if possible
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    a[1] = 1
    mask = 3
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i, mask))
        if i != j # a[i] is undef (and could be #undef)
            a[i] = a[j]
        end
        a[j] = i
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)


## randcycle & randcycle!

"""
    randcycle([rng=default_rng(),] n::Integer)

Construct a random cyclic permutation of length `n`. The optional `rng`
argument specifies a random number generator, see [Random Numbers](@ref).
The element type of the result is the same as the type of `n`.

Here, a "cyclic permutation" means that all of the elements lie within
a single cycle.  If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
which are sampled uniformly.  If `n == 0`, `randcycle` returns an empty vector.

[`randcycle!`](@ref) is an in-place variant of this function.

!!! compat "Julia 1.1"
    In Julia 1.1 and above, `randcycle` returns a vector `v` with
    `eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.

# Examples
```jldoctest
julia> randcycle(Xoshiro(123), 6)
6-element Vector{Int64}:
 5
 4
 2
 6
 3
 1
```
"""
randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))
randcycle(n::Integer) = randcycle(default_rng(), n)

"""
    randcycle!([rng=default_rng(),] A::Array{<:Integer})

Construct in `A` a random cyclic permutation of length `n = length(A)`.
The optional `rng` argument specifies a random number generator, see
[Random Numbers](@ref).

Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
which are sampled uniformly.  If `A` is empty, `randcycle!` leaves it unchanged.

[`randcycle`](@ref) is a variant of this function that allocates a new vector.

# Examples
```jldoctest
julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
6-element Vector{Int64}:
 5
 4
 2
 6
 3
 1
```
"""
function randcycle!(r::AbstractRNG, a::Array{<:Integer})
    # keep it consistent with `shuffle!` and `randperm!` if possible
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    a[1] = 1
    mask = 3
    # Sattolo's algorithm:
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i-1, mask))
        a[i] = a[j]
        a[j] = i
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	## rand!(::BitArray) && bitrand
4
5	function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})	138,234✔
6	isempty(B) && return B	138,234✔
7	Bc = B.chunks	135,275✔
8	rand!(rng, Bc)	135,275✔
9	Bc[end] &= Base._msk_end(B)	135,275✔
10	return B	135,275✔
11	end
12
13	"""
14	bitrand([rng=default_rng()], [dims...])
15
16	Generate a `BitArray` of random boolean values.
17
18	# Examples
19	```jldoctest
20	julia> bitrand(Xoshiro(123), 10)
21	10-element BitVector:
22	0
23	1
24	0
25	1
26	0
27	1
28	0
29	0
30	1
31	1
32	```
33	"""
34	bitrand(r::AbstractRNG, dims::Dims) = rand!(r, BitArray(undef, dims))	×
35	bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))	13✔
36
37	bitrand(dims::Dims) = rand!(BitArray(undef, dims))	27✔
38	bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))	86,294✔
39
40
41	## randstring (often useful for temporary filenames/dirnames)
42
43	"""
44	randstring([rng=default_rng()], [chars], [len=8])
45
46	Create a random string of length `len`, consisting of characters from
47	`chars`, which defaults to the set of upper- and lower-case letters
48	and the digits 0-9. The optional `rng` argument specifies a random
49	number generator, see [Random Numbers](@ref).
50
51	# Examples
52	```jldoctest
53	julia> Random.seed!(3); randstring()
54	"Lxz5hUwn"
55
56	julia> randstring(Xoshiro(3), 'a':'z', 6)
57	"iyzcsm"
58
59	julia> randstring("ACGT")
60	"TGCTCCTC"
61	```
62
63	!!! note
64	`chars` can be any collection of characters, of type `Char` or
65	`UInt8` (more efficient), provided [`rand`](@ref) can randomly
66	pick characters from it.
67	"""
68	function randstring end
69
70	let b = UInt8['0':'9';'A':'Z';'a':'z']
71	global randstring
72
73	function randstring(r::AbstractRNG, chars=b, n::Integer=8)	106,922✔
74	T = eltype(chars)	106,922✔
75	if T === UInt8	106,911✔
76	str = Base._string_n(n)	105,802✔
77	GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)	105,802✔
78	return str	105,802✔
79	else
80	v = Vector{T}(undef, n)	1,109✔
81	rand!(r, v, chars)	1,109✔
82	return String(v)	1,109✔
83	end
84	end
85
86	randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)	1,105✔
87	randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)	200,443✔
88	randstring(n::Integer) = randstring(default_rng(), b, n)	4,469✔
89	end
90
91
92	## randsubseq & randsubseq!
93
94	# Fill S (resized as needed) with a random subsequence of A, where
95	# each element of A is included in S with independent probability p.
96	# (Note that this is different from the problem of finding a random
97	# size-m subset of A where m is fixed!)
98	function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)	1,916✔
99	require_one_based_indexing(S, A)	1,916✔
100	0 <= p <= 1 \|\| throw(ArgumentError("probability $p not in [0,1]"))	1,916✔
101	n = length(A)	1,916✔
102	p == 1 && return copyto!(resize!(S, n), A)	1,916✔
103	empty!(S)	1,894✔
104	p == 0 && return S	1,894✔
105	nexpected = p * length(A)	1,888✔
106	sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))	1,888✔
107	if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better	1,888✔
108	for i = 1:n	3,608✔
109	rand(r) <= p && push!(S, A[i])	42,084,793✔
110	end	84,167,782✔
111	else
112	# Skip through A, in order, from each element i to the next element i+s
113	# included in S. The probability that the next included element is
114	# s==k (k > 0) is (1-p)^(k-1) * p, and hence the probability (CDF) that
115	# s is in {1,...,k} is 1-(1-p)^k = F(k). Thus, we can draw the skip s
116	# from this probability distribution via the discrete inverse-transform
117	# method: s = ceil(F^{-1}(u)) where u = rand(), which is simply
118	# s = ceil(log(rand()) / log1p(-p)).
119	# -log(rand()) is an exponential variate, so can use randexp().
120	L = -1 / log1p(-p) # L > 0	84✔
121	i = 0	84✔
122	while true	185,417✔
123	s = randexp(r) * L	185,417✔
124	s >= n - i && return S # compare before ceil to avoid overflow	185,417✔
125	push!(S, A[i += ceil(Int,s)])	185,333✔
126	end	185,333✔
127	# [This algorithm is similar in spirit to, but much simpler than,
128	# the one by Vitter for a related problem in "Faster methods for
129	# random sampling," Comm. ACM Magazine 7, 703-718 (1984).]
130	end
131	return S	1,804✔
132	end
133
134	"""
135	randsubseq!([rng=default_rng(),] S, A, p)
136
137	Like [`randsubseq`](@ref), but the results are stored in `S`
138	(which is resized as needed).
139
140	# Examples
141	```jldoctest
142	julia> S = Int64[];
143
144	julia> randsubseq!(Xoshiro(123), S, 1:8, 0.3)
145	2-element Vector{Int64}:
146	4
147	7
148
149	julia> S
150	2-element Vector{Int64}:
151	4
152	7
153	```
154	"""
155	randsubseq!(S::AbstractArray, A::AbstractArray, p::Real) = randsubseq!(default_rng(), S, A, p)	×
156
157	randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =	1,912✔
158	randsubseq!(r, T[], A, p)
159
160	"""
161	randsubseq([rng=default_rng(),] A, p) -> Vector
162
163	Return a vector consisting of a random subsequence of the given array `A`, where each
164	element of `A` is included (in order) with independent probability `p`. (Complexity is
165	linear in `p*length(A)`, so this function is efficient even if `p` is small and `A` is
166	large.) Technically, this process is known as "Bernoulli sampling" of `A`.
167
168	# Examples
169	```jldoctest
170	julia> randsubseq(Xoshiro(123), 1:8, 0.3)
171	2-element Vector{Int64}:
172	4
173	7
174	```
175	"""
176	randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)	1,087✔
177
178
179	## rand Less Than Masked 52 bits (helper function)
180
181	"Return a sampler generating a random `Int` (masked with `mask`) in ``[0, n)``, when `n <= 2^52`."
182	ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))	986,112✔
183
184	## shuffle & shuffle!
185
186	"""
187	shuffle!([rng=default_rng(),] v::AbstractArray)
188
189	In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
190	optionally supplying the random-number generator `rng`.
191
192	# Examples
193	```jldoctest
194	julia> shuffle!(Xoshiro(123), Vector(1:10))
195	10-element Vector{Int64}:
196	5
197	4
198	2
199	3
200	6
201	10
202	8
203	1
204	9
205	7
206	```
207	"""
208	function shuffle!(r::AbstractRNG, a::AbstractArray)	50,032✔
209	# keep it consistent with `randperm!` and `randcycle!` if possible
210	require_one_based_indexing(a)	50,032✔
211	n = length(a)	50,032✔
212	@assert n <= Int64(2)^52	50,032✔
213	n == 0 && return a	50,032✔
214	mask = 3	50,030✔
215	@inbounds for i = 2:n	100,059✔
216	j = 1 + rand(r, ltm52(i, mask))	1,349,699✔
217	a[i], a[j] = a[j], a[i]	951,789✔
218	i == 1 + mask && (mask = 2 * mask + 1)	951,589✔
219	end	1,853,149✔
220	return a	50,030✔
221	end
222
223	shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)	4✔
224
225	"""
226	shuffle([rng=default_rng(),] v::AbstractArray)
227
228	Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
229	number generator (see [Random Numbers](@ref)).
230	To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
231	indices, see [`randperm`](@ref).
232
233	# Examples
234	```jldoctest
235	julia> shuffle(Xoshiro(123), Vector(1:10))
236	10-element Vector{Int64}:
237	5
238	4
239	2
240	3
241	6
242	10
243	8
244	1
245	9
246	7
247	```
248	"""
249	shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))	20✔
250	shuffle(a::AbstractArray) = shuffle(default_rng(), a)	8✔
251
252	shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))	×
253
254	## randperm & randperm!
255
256	"""
257	randperm([rng=default_rng(),] n::Integer)
258
259	Construct a random permutation of length `n`. The optional `rng`
260	argument specifies a random number generator (see [Random
261	Numbers](@ref)). The element type of the result is the same as the type
262	of `n`.
263
264	To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
265	[`shuffle!`](@ref).
266
267	!!! compat "Julia 1.1"
268	In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
269	while in Julia 1.0 `eltype(v) == Int`.
270
271	# Examples
272	```jldoctest
273	julia> randperm(Xoshiro(123), 4)
274	4-element Vector{Int64}:
275	1
276	4
277	2
278	3
279	```
280	"""
281	randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))	67✔
282	randperm(n::Integer) = randperm(default_rng(), n)	59✔
283
284	"""
285	randperm!([rng=default_rng(),] A::Array{<:Integer})
286
287	Construct in `A` a random permutation of length `length(A)`. The
288	optional `rng` argument specifies a random number generator (see
289	[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
290	[`shuffle`](@ref) or [`shuffle!`](@ref).
291
292	# Examples
293	```jldoctest
294	julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
295	4-element Vector{Int64}:
296	1
297	4
298	2
299	3
300	```
301	"""
302	function randperm!(r::AbstractRNG, a::Array{<:Integer})	71✔
303	# keep it consistent with `shuffle!` and `randcycle!` if possible
304	n = length(a)	71✔
305	@assert n <= Int64(2)^52	71✔
306	n == 0 && return a	71✔
307	a[1] = 1	69✔
308	mask = 3	69✔
309	@inbounds for i = 2:n	137✔
310	j = 1 + rand(r, ltm52(i, mask))	34,259✔
311	if i != j # a[i] is undef (and could be #undef)	34,217✔
312	a[i] = a[j]	34,093✔
313	end
314	a[j] = i	34,217✔
315	i == 1 + mask && (mask = 2 * mask + 1)	34,217✔
316	end	68,366✔
317	return a	69✔
318	end
319
320	randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)	2✔
321
322
323	## randcycle & randcycle!
324
325	"""
326	randcycle([rng=default_rng(),] n::Integer)
327
328	Construct a random cyclic permutation of length `n`. The optional `rng`
329	argument specifies a random number generator, see [Random Numbers](@ref).
330	The element type of the result is the same as the type of `n`.
331
332	Here, a "cyclic permutation" means that all of the elements lie within
333	a single cycle. If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
334	which are sampled uniformly. If `n == 0`, `randcycle` returns an empty vector.
335
336	[`randcycle!`](@ref) is an in-place variant of this function.
337
338	!!! compat "Julia 1.1"
339	In Julia 1.1 and above, `randcycle` returns a vector `v` with
340	`eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.
341
342	# Examples
343	```jldoctest
344	julia> randcycle(Xoshiro(123), 6)
345	6-element Vector{Int64}:
346	5
347	4
348	2
349	6
350	3
351	1
352	```
353	"""
354	randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))	25✔
355	randcycle(n::Integer) = randcycle(default_rng(), n)	21✔
356
357	"""
358	randcycle!([rng=default_rng(),] A::Array{<:Integer})
359
360	Construct in `A` a random cyclic permutation of length `n = length(A)`.
361	The optional `rng` argument specifies a random number generator, see
362	[Random Numbers](@ref).
363
364	Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
365	If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
366	which are sampled uniformly. If `A` is empty, `randcycle!` leaves it unchanged.
367
368	[`randcycle`](@ref) is a variant of this function that allocates a new vector.
369
370	# Examples
371	```jldoctest
372	julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
373	6-element Vector{Int64}:
374	5
375	4
376	2
377	6
378	3
379	1
380	```
381	"""
382	function randcycle!(r::AbstractRNG, a::Array{<:Integer})	31✔
383	# keep it consistent with `shuffle!` and `randperm!` if possible
384	n = length(a)	31✔
385	@assert n <= Int64(2)^52	31✔
386	n == 0 && return a	31✔
387	a[1] = 1	31✔
388	mask = 3	31✔
389	# Sattolo's algorithm:
390	@inbounds for i = 2:n	62✔
391	j = 1 + rand(r, ltm52(i-1, mask))	352✔
392	a[i] = a[j]	306✔
393	a[j] = i	306✔
394	i == 1 + mask && (mask = 2 * mask + 1)	306✔
395	end	581✔
396	return a	31✔
397	end
398
399	randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)	2✔

JuliaLang / julia / #37636

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous