1 #if !defined HAVE_PERMRAND_H__
2 #define HAVE_PERMRAND_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8 #include "aux0/swap.h"
9 #include "aux0/rand-idx.h"
10 #include "fxttypes.h"
11
12
13 template <typename Type>
random_permute(Type * f,ulong n)14 void random_permute(Type *f, ulong n)
15 // Randomly permute the elements of f[].
16 {
17 #if 1
18 for (ulong k=n; k>1; --k)
19 {
20 const ulong i = rand_idx(k);
21 swap2(f[k-1], f[i]);
22 }
23
24 #else
25
26 for (ulong k=1; k<n; ++k)
27 {
28 const ulong i = rand_idx(k+1);
29 swap2(f[k], f[i]);
30 }
31 #endif
32 }
33 // -------------------------
34
random_permutation(ulong * f,ulong n)35 inline void random_permutation(ulong *f, ulong n)
36 // Create a random permutation.
37 {
38 for (ulong k=0; k<n; ++k) f[k] = k;
39 random_permute(f, n);
40 }
41 // -------------------------
42
43
44 template <typename Type>
random_permute_positions(Type * f,ulong np,const ulong * ps)45 void random_permute_positions(Type *f, ulong np, const ulong *ps)
46 // Randomly permute the np elements f[ps[0]], f[ps[1], ..., f[ps[np-1]].
47 {
48 for (ulong k=1; k<np; ++k)
49 {
50 const ulong i = rand_idx(k+1);
51 swap2(f[ps[k]], f[ps[i]]);
52 }
53 }
54 // -------------------------
55
56
57
58 #endif // !defined HAVE_PERMRAND_H__
59