pf_random_perm_at Interface

public interface pf_random_perm_at

Element k of a uniform-looking permutation of 1 .. m, addressed by its coordinates.

The permutation counterpart of pf_random_at: a pure function of (seed, m, k), computed in constant time and constant memory, touching no array. Element k depends on no other element, so a loop over k may be run in any order, on any number of threads, and gives the same answer -- which is the property the whole module exists for, extended from draws to permutations.

!$omp parallel do
do k = 1, m
    perm(k) = pf_random_perm_at(seed, m, k)      ! same result at any thread count
end do

The first n values are a uniform random n-subset of 1 .. m, so a subset needs no separate machinery and no memory: ask for k = 1 .. n. Prefix consistency follows for free -- a size-3 subset is a prefix of a size-6 one from the same (seed, m) -- and a subset at n == m is the permutation, rather than merely agreeing with it.

m and k share their kind (integer(int32) or integer(int64)) and the result follows them; seed is always integer(int64). k outside [1, m] is clamped rather than reported, the same convention draw_or_1 uses and for the same reason: this is pure elemental and has no way to abort.

Uniformity comes in two grades, split at m = 20, and the split is visible in pf_random_perm_algorithm.

For m <= 20 the result is exactly uniform over all m! permutations -- one exactly uniform rank in [0, m!) composed with a bijection onto S_m, so this is a property of the construction rather than a measurement. 20 is where it stops because 20! is the last factorial an integer(int64) holds.

For m >= 21 a 64-bit seed cannot address m! permutations at all, so exact uniformity is not available to any construction with this signature. What is measured instead is that the result is indistinguishable from a uniform permutation under an all-cells chi-square, an order-4 tuple statistic, a parity test over the alternating group, and fixed-point, cycle-structure, position-uniformity, subset-membership and structural tests.

Consecutive m are independent, in both regimes. Asking for a permutation of 5 and one of 6 under the same seed gives two unrelated answers rather than two views of one draw.


Module Procedures

private pure elemental function pf_random_perm_at_i32(seed, m, k) result(r)

pf_random_perm_at for integer(int32) population size and index.

The result is inside [1, m] by construction, so narrowing the int64 worker's answer is exact -- the same argument pf_random_int_at_i32 rests on.

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(in) :: seed

the permutation family's seed
integer(kind=int32), intent(in) :: m

population size; the permutation is of 1 .. m
integer(kind=int32), intent(in) :: k

1-based position; clamped into [1, m]

Return Value integer(kind=int32)

element k of that permutation

private pure elemental function pf_random_perm_at_i64(seed, m, k) result(r)

pf_random_perm_at for integer(int64) population size and index.

Arguments

Type IntentOptional Attributes Name
integer(kind=int64), intent(in) :: seed

the permutation family's seed
integer(kind=int64), intent(in) :: m

population size; the permutation is of 1 .. m
integer(kind=int64), intent(in) :: k

1-based position; clamped into [1, m]

Return Value integer(kind=int64)

element k of that permutation