WFMath  1.0.1
shuffle.h
1 // randgen.h (random number functions)
2 //
3 // The WorldForge Project
4 // Copyright (C) 2002 The WorldForge Project
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 2 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 //
20 // For information about WorldForge and its authors, please contact
21 // the Worldforge Web Site at http://www.worldforge.org.
22 
23 // Author: Ron Steinke
24 // Created: 2002-5-23
25 
26 #ifndef WFMATH_SHUFFLE_H
27 #define WFMATH_SHUFFLE_H
28 
29 #include <wfmath/MersenneTwister.h>
30 
31 #include <vector>
32 
33 namespace WFMath {
34 
36 
39 template<class C>
40 void Shuffle(std::vector<C>& v) // need vector for random access
41 {
42  typedef typename std::vector<C>::size_type size_type;
43  size_type pos = v.size();
44 
45  if(!pos) // handle size() == 0 nicely
46  return;
47 
48  // This swaps each element with one of the ones before
49  // it, starting with the last element. Essentially,
50  // this generates an operation from the permutation
51  // group of size() elements, and applies it to the
52  // vector. Note that the loop only executes size() - 1
53  // times, as element 0 has nothing to swap with.
54  while(--pos) {
55  size_type new_pos = MTRand::instance.randInt(pos); // 0 <= new_pos <= pos
56  if(new_pos == pos)
57  continue;
58  C tmp = v[pos];
59  v[pos] = v[new_pos];
60  v[new_pos] = tmp;
61  }
62 }
63 
64 } // namespace WFMath
65 
66 #endif // WFMATH_SHUFFLE_H