#37997

Committed 29 Jan 2025 02:08AM UTC coverage: 17.283% (-68.7%) from 85.981%

Build # #37997

Build Type

push

local

Committed by

web-flow

Commit Message

bpart: Start enforcing min_world for global variable definitions (#57150)

This is the analog of #57102 for global variables. Unlike for consants,
there is no automatic global backdate mechanism. The reasoning for this
is that global variables can be declared at any time, unlike constants
which can only be decalared once their value is available. As a result
code patterns using `Core.eval` to declare globals are rarer and likely
incorrect.

Run Details

1 of 22 new or added lines in 3 files covered. (4.55%)

31430 existing lines in 188 files now uncovered.

7903 of 45728 relevant lines covered (17.28%)

98663.7 hits per line

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

0.92

/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

function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})
    old_count = count(a)
    len = length(a)
    uncommon_value = 2old_count <= len
    fuel = uncommon_value ? old_count : len - old_count
    fuel == 0 && return a
    a .= !uncommon_value
    while fuel > 0
        k = rand(r, eachindex(a))
        fuel -= a[k] != uncommon_value
        a[k] = uncommon_value
    end
    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
UNCOV 5	function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})	×
UNCOV 6	isempty(B) && return B	×
UNCOV 7	Bc = B.chunks	×
UNCOV 8	rand!(rng, Bc)	×
UNCOV 9	Bc[end] &= Base._msk_end(B)	×
UNCOV 10	return B	×
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))	×
UNCOV 35	bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))	×
36
UNCOV 37	bitrand(dims::Dims) = rand!(BitArray(undef, dims))	×
UNCOV 38	bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))	×
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
UNCOV 73	function randstring(r::AbstractRNG, chars=b, n::Integer=8)	×
UNCOV 74	T = eltype(chars)	×
UNCOV 75	if T === UInt8	×
UNCOV 76	str = Base._string_n(n)	×
UNCOV 77	GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)	×
UNCOV 78	return str	×
79	else
UNCOV 80	v = Vector{T}(undef, n)	×
UNCOV 81	rand!(r, v, chars)	×
UNCOV 82	return String(v)	×
83	end
84	end
85
UNCOV 86	randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)	×
UNCOV 87	randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)	×
88	randstring(n::Integer) = randstring(default_rng(), b, n)	84✔
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!)
UNCOV 98	function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)	×
UNCOV 99	require_one_based_indexing(S, A)	×
UNCOV 100	0 <= p <= 1 \|\| throw(ArgumentError("probability $p not in [0,1]"))	×
UNCOV 101	n = length(A)	×
UNCOV 102	p == 1 && return copyto!(resize!(S, n), A)	×
UNCOV 103	empty!(S)	×
UNCOV 104	p == 0 && return S	×
UNCOV 105	nexpected = p * length(A)	×
UNCOV 106	sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))	×
UNCOV 107	if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better	×
UNCOV 108	for i = 1:n	×
UNCOV 109	rand(r) <= p && push!(S, A[i])	×
UNCOV 110	end	×
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().
UNCOV 120	L = -1 / log1p(-p) # L > 0	×
UNCOV 121	i = 0	×
UNCOV 122	while true	×
UNCOV 123	s = randexp(r) * L	×
UNCOV 124	s >= n - i && return S # compare before ceil to avoid overflow	×
UNCOV 125	push!(S, A[i += ceil(Int,s)])	×
UNCOV 126	end	×
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
UNCOV 131	return S	×
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
UNCOV 157	randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =	×
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	"""
UNCOV 176	randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)	×
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`."
UNCOV 182	ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))	×
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	"""
UNCOV 208	function shuffle!(r::AbstractRNG, a::AbstractArray)	×
209	# keep it consistent with `randperm!` and `randcycle!` if possible
UNCOV 210	require_one_based_indexing(a)	×
UNCOV 211	n = length(a)	×
UNCOV 212	@assert n <= Int64(2)^52	×
UNCOV 213	n == 0 && return a	×
UNCOV 214	mask = 3	×
UNCOV 215	@inbounds for i = 2:n	×
UNCOV 216	j = 1 + rand(r, ltm52(i, mask))	×
UNCOV 217	a[i], a[j] = a[j], a[i]	×
UNCOV 218	i == 1 + mask && (mask = 2 * mask + 1)	×
UNCOV 219	end	×
UNCOV 220	return a	×
221	end
222
UNCOV 223	function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})	×
UNCOV 224	old_count = count(a)	×
UNCOV 225	len = length(a)	×
UNCOV 226	uncommon_value = 2old_count <= len	×
UNCOV 227	fuel = uncommon_value ? old_count : len - old_count	×
UNCOV 228	fuel == 0 && return a	×
UNCOV 229	a .= !uncommon_value	×
UNCOV 230	while fuel > 0	×
UNCOV 231	k = rand(r, eachindex(a))	×
UNCOV 232	fuel -= a[k] != uncommon_value	×
UNCOV 233	a[k] = uncommon_value	×
UNCOV 234	end	×
UNCOV 235	a	×
236	end
237
UNCOV 238	shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)	×
239
240	"""
241	shuffle([rng=default_rng(),] v::AbstractArray)
242
243	Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
244	number generator (see [Random Numbers](@ref)).
245	To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
246	indices, see [`randperm`](@ref).
247
248	# Examples
249	```jldoctest
250	julia> shuffle(Xoshiro(123), Vector(1:10))
251	10-element Vector{Int64}:
252	5
253	4
254	2
255	3
256	6
257	10
258	8
259	1
260	9
261	7
262	```
263	"""
UNCOV 264	shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))	×
UNCOV 265	shuffle(a::AbstractArray) = shuffle(default_rng(), a)	×
266
267	shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))	×
268
269	## randperm & randperm!
270
271	"""
272	randperm([rng=default_rng(),] n::Integer)
273
274	Construct a random permutation of length `n`. The optional `rng`
275	argument specifies a random number generator (see [Random
276	Numbers](@ref)). The element type of the result is the same as the type
277	of `n`.
278
279	To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
280	[`shuffle!`](@ref).
281
282	!!! compat "Julia 1.1"
283	In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
284	while in Julia 1.0 `eltype(v) == Int`.
285
286	# Examples
287	```jldoctest
288	julia> randperm(Xoshiro(123), 4)
289	4-element Vector{Int64}:
290	1
291	4
292	2
293	3
294	```
295	"""
UNCOV 296	randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))	×
UNCOV 297	randperm(n::Integer) = randperm(default_rng(), n)	×
298
299	"""
300	randperm!([rng=default_rng(),] A::Array{<:Integer})
301
302	Construct in `A` a random permutation of length `length(A)`. The
303	optional `rng` argument specifies a random number generator (see
304	[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
305	[`shuffle`](@ref) or [`shuffle!`](@ref).
306
307	# Examples
308	```jldoctest
309	julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
310	4-element Vector{Int64}:
311	1
312	4
313	2
314	3
315	```
316	"""
UNCOV 317	function randperm!(r::AbstractRNG, a::Array{<:Integer})	×
318	# keep it consistent with `shuffle!` and `randcycle!` if possible
UNCOV 319	n = length(a)	×
UNCOV 320	@assert n <= Int64(2)^52	×
UNCOV 321	n == 0 && return a	×
UNCOV 322	a[1] = 1	×
UNCOV 323	mask = 3	×
UNCOV 324	@inbounds for i = 2:n	×
UNCOV 325	j = 1 + rand(r, ltm52(i, mask))	×
UNCOV 326	if i != j # a[i] is undef (and could be #undef)	×
UNCOV 327	a[i] = a[j]	×
328	end
UNCOV 329	a[j] = i	×
UNCOV 330	i == 1 + mask && (mask = 2 * mask + 1)	×
UNCOV 331	end	×
UNCOV 332	return a	×
333	end
334
UNCOV 335	randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)	×
336
337
338	## randcycle & randcycle!
339
340	"""
341	randcycle([rng=default_rng(),] n::Integer)
342
343	Construct a random cyclic permutation of length `n`. The optional `rng`
344	argument specifies a random number generator, see [Random Numbers](@ref).
345	The element type of the result is the same as the type of `n`.
346
347	Here, a "cyclic permutation" means that all of the elements lie within
348	a single cycle. If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
349	which are sampled uniformly. If `n == 0`, `randcycle` returns an empty vector.
350
351	[`randcycle!`](@ref) is an in-place variant of this function.
352
353	!!! compat "Julia 1.1"
354	In Julia 1.1 and above, `randcycle` returns a vector `v` with
355	`eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.
356
357	# Examples
358	```jldoctest
359	julia> randcycle(Xoshiro(123), 6)
360	6-element Vector{Int64}:
361	5
362	4
363	2
364	6
365	3
366	1
367	```
368	"""
UNCOV 369	randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))	×
UNCOV 370	randcycle(n::Integer) = randcycle(default_rng(), n)	×
371
372	"""
373	randcycle!([rng=default_rng(),] A::Array{<:Integer})
374
375	Construct in `A` a random cyclic permutation of length `n = length(A)`.
376	The optional `rng` argument specifies a random number generator, see
377	[Random Numbers](@ref).
378
379	Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
380	If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
381	which are sampled uniformly. If `A` is empty, `randcycle!` leaves it unchanged.
382
383	[`randcycle`](@ref) is a variant of this function that allocates a new vector.
384
385	# Examples
386	```jldoctest
387	julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
388	6-element Vector{Int64}:
389	5
390	4
391	2
392	6
393	3
394	1
395	```
396	"""
UNCOV 397	function randcycle!(r::AbstractRNG, a::Array{<:Integer})	×
398	# keep it consistent with `shuffle!` and `randperm!` if possible
UNCOV 399	n = length(a)	×
UNCOV 400	@assert n <= Int64(2)^52	×
UNCOV 401	n == 0 && return a	×
UNCOV 402	a[1] = 1	×
UNCOV 403	mask = 3	×
404	# Sattolo's algorithm:
UNCOV 405	@inbounds for i = 2:n	×
UNCOV 406	j = 1 + rand(r, ltm52(i-1, mask))	×
UNCOV 407	a[i] = a[j]	×
UNCOV 408	a[j] = i	×
UNCOV 409	i == 1 + mask && (mask = 2 * mask + 1)	×
UNCOV 410	end	×
UNCOV 411	return a	×
412	end
413
UNCOV 414	randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)	×

JuliaLang / julia / #37997

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