#38185

Committed 16 Aug 2025 08:28PM UTC coverage: 77.822% (-0.5%) from 78.284%

Build # #38185

Build Type

push

local

Committed by

web-flow

Commit Message

add `shuffle(::NTuple)` to `Random` (#56906)

Coverage Stats

9 of 12 new or added lines in 1 file covered. (75.0%)

453 existing lines in 47 files now uncovered.

48251 of 62002 relevant lines covered (77.82%)

9289181.39 hits per line

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

95.04

/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_argerror(LazyString("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!

function shuffle(rng::AbstractRNG, tup::NTuple{N}) where {N}
    # `@inline` and `@inbounds` are here to help escape analysis eliminate the `Memory` allocation
    #
    # * `@inline` might be necessary because escape analysis relies on everything
    #   touching the `Memory` being inlined because there's no interprocedural escape
    #   analysis yet, relevant WIP PR: https://github.com/JuliaLang/julia/pull/56849
    #
    # * `@inbounds` might be necessary because escape analysis requires any throws of
    #   `BoundsError` to be eliminated as dead code, because `BoundsError` stores the
    #   array itself, making the throw escape the array from the function, relevant
    #   WIP PR: https://github.com/JuliaLang/julia/pull/56167
    @inline let
        # use a narrow integer type to save stack space and prevent heap allocation
        Ind = if N ≤ typemax(UInt8)
            UInt8
        elseif N ≤ typemax(UInt16)
            UInt16
        else
            UInt
        end
        mem = @inbounds randperm!(rng, Memory{Ind}(undef, N))
        function closure(i::Int)
            @inbounds tup[mem[i]]
        end
        ntuple(closure, Val{N}())
    end
end

"""
    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::Union{NTuple,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).

!!! compat "Julia 1.13"
    Shuffling an `NTuple` value requires Julia v1.13 or above.

# 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 end

shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))
shuffle(a::Union{NTuple, 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::AbstractArray{<: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).

!!! compat "Julia 1.13"
    `A isa Array` was required prior to Julia v1.13.

# Examples
```jldoctest
julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
function randperm!(r::AbstractRNG, a::AbstractArray{<:Integer})
    # keep it consistent with `shuffle!` and `randcycle!` if possible
    Base.require_one_based_indexing(a)
    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::AbstractArray{<: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::AbstractArray{<: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.

!!! compat "Julia 1.13"
    `A isa Array` was required prior to Julia v1.13.

# 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::AbstractArray{<:Integer})
    # keep it consistent with `shuffle!` and `randperm!` if possible
    Base.require_one_based_indexing(a)
    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::AbstractArray{<: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})
6	isempty(B) && return B	138,321✔
7	Bc = B.chunks	135,362✔
8	rand!(rng, Bc)	135,362✔
9	Bc[end] &= Base._msk_end(B)	135,362✔
10	return B	135,362✔
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)))	16✔
36
37	bitrand(dims::Dims) = rand!(BitArray(undef, dims))	41✔
38	bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))	86,422✔
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)	1,122✔
74	T = eltype(chars)	105,752✔
75	if T === UInt8	105,741✔
76	str = Base._string_n(n)	105,808✔
77	GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)	105,892✔
78	return str	105,655✔
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,333✔
88	randstring(n::Integer) = randstring(default_rng(), b, n)	4,527✔
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)	3,032✔
99	require_one_based_indexing(S, A)	3,032✔
100	0 <= p <= 1 \|\| _throw_argerror(LazyString("probability ", p, " not in [0,1]"))	3,032✔
101	n = length(A)	3,032✔
102	p == 1 && return copyto!(resize!(S, n), A)	3,032✔
103	empty!(S)	3,010✔
104	p == 0 && return S	3,010✔
105	nexpected = p * length(A)	3,001✔
106	sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))	3,001✔
107	if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better	3,001✔
108	for i = 1:n	2,847✔
109	rand(r) <= p && push!(S, A[i])	42,400,821✔
110	end	84,798,795✔
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	154✔
121	i = 0	154✔
122	while true	229,419✔
123	s = randexp(r) * L	229,419✔
124	s >= n - i && return S # compare before ceil to avoid overflow	229,419✔
125	push!(S, A[i += ceil(Int,s)])	229,265✔
126	end	229,265✔
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	2,847✔
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} =	3,028✔
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)	2,071✔
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)))	54,170✔
183
184	## shuffle & shuffle!
185
186	function shuffle(rng::AbstractRNG, tup::NTuple{N}) where {N}	19✔
187	# `@inline` and `@inbounds` are here to help escape analysis eliminate the `Memory` allocation
188	#
189	# * `@inline` might be necessary because escape analysis relies on everything
190	# touching the `Memory` being inlined because there's no interprocedural escape
191	# analysis yet, relevant WIP PR: https://github.com/JuliaLang/julia/pull/56849
192	#
193	# * `@inbounds` might be necessary because escape analysis requires any throws of
194	# `BoundsError` to be eliminated as dead code, because `BoundsError` stores the
195	# array itself, making the throw escape the array from the function, relevant
196	# WIP PR: https://github.com/JuliaLang/julia/pull/56167
197	@inline let	22✔
198	# use a narrow integer type to save stack space and prevent heap allocation
199	Ind = if N ≤ typemax(UInt8)	22✔
200	UInt8	22✔
NEW 201	elseif N ≤ typemax(UInt16)	×
NEW 202	UInt16	×
203	else
NEW 204	UInt	×
205	end
206	mem = @inbounds randperm!(rng, Memory{Ind}(undef, N))	200✔
207	function closure(i::Int)	22✔
208	@inbounds tup[mem[i]]	21✔
209	end
210	ntuple(closure, Val{N}())	22✔
211	end
212	end
213
214	"""
215	shuffle!([rng=default_rng(),] v::AbstractArray)
216
217	In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
218	optionally supplying the random-number generator `rng`.
219
220	# Examples
221	```jldoctest
222	julia> shuffle!(Xoshiro(123), Vector(1:10))
223	10-element Vector{Int64}:
224	5
225	4
226	2
227	3
228	6
229	10
230	8
231	1
232	9
233	7
234	```
235	"""
236	function shuffle!(r::AbstractRNG, a::AbstractArray)	2,032✔
237	# keep it consistent with `randperm!` and `randcycle!` if possible
238	require_one_based_indexing(a)	2,032✔
239	n = length(a)	2,032✔
240	@assert n <= Int64(2)^52	2,032✔
241	n == 0 && return a	2,032✔
242	mask = 3	2,030✔
243	@inbounds for i = 2:n	2,030✔
244	j = 1 + rand(r, ltm52(i, mask))	19,361✔
245	a[i], a[j] = a[j], a[i]	19,269✔
246	i == 1 + mask && (mask = 2 * mask + 1)	19,269✔
247	end	36,509✔
248	return a	2,030✔
249	end
250
251	function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})	50,004✔
252	old_count = count(a)	50,004✔
253	len = length(a)	50,004✔
254	uncommon_value = 2old_count <= len	50,004✔
255	fuel = uncommon_value ? old_count : len - old_count	50,008✔
256	fuel == 0 && return a	50,004✔
257	a .= !uncommon_value	50,024✔
258	while fuel > 0	152,689✔
259	k = rand(r, eachindex(a))	205,370✔
260	fuel -= a[k] != uncommon_value	102,685✔
261	a[k] = uncommon_value	102,685✔
262	end	102,685✔
263	a	50,004✔
264	end
265
266	shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)	2,004✔
267
268	"""
269	shuffle([rng=default_rng(),] v::Union{NTuple,AbstractArray})
270
271	Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
272	number generator (see [Random Numbers](@ref)).
273	To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
274	indices, see [`randperm`](@ref).
275
276	!!! compat "Julia 1.13"
277	Shuffling an `NTuple` value requires Julia v1.13 or above.
278
279	# Examples
280	```jldoctest
281	julia> shuffle(Xoshiro(123), Vector(1:10))
282	10-element Vector{Int64}:
283	5
284	4
285	2
286	3
287	6
288	10
289	8
290	1
291	9
292	7
293	```
294	"""
295	function shuffle end
296
297	shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))	21✔
298	shuffle(a::Union{NTuple, AbstractArray}) = shuffle(default_rng(), a)	31✔
299
300	shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))	×
301
302	## randperm & randperm!
303
304	"""
305	randperm([rng=default_rng(),] n::Integer)
306
307	Construct a random permutation of length `n`. The optional `rng`
308	argument specifies a random number generator (see [Random
309	Numbers](@ref)). The element type of the result is the same as the type
310	of `n`.
311
312	To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
313	[`shuffle!`](@ref).
314
315	!!! compat "Julia 1.1"
316	In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
317	while in Julia 1.0 `eltype(v) == Int`.
318
319	# Examples
320	```jldoctest
321	julia> randperm(Xoshiro(123), 4)
322	4-element Vector{Int64}:
323	1
324	4
325	2
326	3
327	```
328	"""
329	randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))	67✔
330	randperm(n::Integer) = randperm(default_rng(), n)	59✔
331
332	"""
333	randperm!([rng=default_rng(),] A::AbstractArray{<:Integer})
334
335	Construct in `A` a random permutation of length `length(A)`. The
336	optional `rng` argument specifies a random number generator (see
337	[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
338	[`shuffle`](@ref) or [`shuffle!`](@ref).
339
340	!!! compat "Julia 1.13"
341	`A isa Array` was required prior to Julia v1.13.
342
343	# Examples
344	```jldoctest
345	julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
346	4-element Vector{Int64}:
347	1
348	4
349	2
350	3
351	```
352	"""
353	function randperm!(r::AbstractRNG, a::AbstractArray{<:Integer})	77✔
354	# keep it consistent with `shuffle!` and `randcycle!` if possible
355	Base.require_one_based_indexing(a)	99✔
356	n = length(a)	99✔
357	@assert n <= Int64(2)^52	99✔
358	n == 0 && return a	99✔
359	a[1] = 1	96✔
360	mask = 3	96✔
361	@inbounds for i = 2:n	96✔
362	j = 1 + rand(r, ltm52(i, mask))	34,596✔
363	if i != j # a[i] is undef (and could be #undef)	34,542✔
364	a[i] = a[j]	34,359✔
365	end
366	a[j] = i	34,542✔
367	i == 1 + mask && (mask = 2 * mask + 1)	34,542✔
368	end	68,989✔
369	return a	96✔
370	end
371
372	randperm!(a::AbstractArray{<:Integer}) = randperm!(default_rng(), a)	4✔
373
374
375	## randcycle & randcycle!
376
377	"""
378	randcycle([rng=default_rng(),] n::Integer)
379
380	Construct a random cyclic permutation of length `n`. The optional `rng`
381	argument specifies a random number generator, see [Random Numbers](@ref).
382	The element type of the result is the same as the type of `n`.
383
384	Here, a "cyclic permutation" means that all of the elements lie within
385	a single cycle. If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
386	which are sampled uniformly. If `n == 0`, `randcycle` returns an empty vector.
387
388	[`randcycle!`](@ref) is an in-place variant of this function.
389
390	!!! compat "Julia 1.1"
391	In Julia 1.1 and above, `randcycle` returns a vector `v` with
392	`eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.
393
394	# Examples
395	```jldoctest
396	julia> randcycle(Xoshiro(123), 6)
397	6-element Vector{Int64}:
398	5
399	4
400	2
401	6
402	3
403	1
404	```
405	"""
406	randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))	25✔
407	randcycle(n::Integer) = randcycle(default_rng(), n)	21✔
408
409	"""
410	randcycle!([rng=default_rng(),] A::AbstractArray{<:Integer})
411
412	Construct in `A` a random cyclic permutation of length `n = length(A)`.
413	The optional `rng` argument specifies a random number generator, see
414	[Random Numbers](@ref).
415
416	Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
417	If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
418	which are sampled uniformly. If `A` is empty, `randcycle!` leaves it unchanged.
419
420	[`randcycle`](@ref) is a variant of this function that allocates a new vector.
421
422	!!! compat "Julia 1.13"
423	`A isa Array` was required prior to Julia v1.13.
424
425	# Examples
426	```jldoctest
427	julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
428	6-element Vector{Int64}:
429	5
430	4
431	2
432	6
433	3
434	1
435	```
436	"""
437	function randcycle!(r::AbstractRNG, a::AbstractArray{<:Integer})	37✔
438	# keep it consistent with `shuffle!` and `randperm!` if possible
439	Base.require_one_based_indexing(a)	37✔
440	n = length(a)	37✔
441	@assert n <= Int64(2)^52	37✔
442	n == 0 && return a	37✔
443	a[1] = 1	37✔
444	mask = 3	37✔
445	# Sattolo's algorithm:
446	@inbounds for i = 2:n	37✔
447	j = 1 + rand(r, ltm52(i-1, mask))	490✔
448	a[i] = a[j]	360✔
449	a[j] = i	360✔
450	i == 1 + mask && (mask = 2 * mask + 1)	360✔
451	end	683✔
452	return a	37✔
453	end
454
455	randcycle!(a::AbstractArray{<:Integer}) = randcycle!(default_rng(), a)	4✔

JuliaLang / julia / #38185

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