WFMath 1.0.2
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
33namespace WFMath {
34
36
39template<class C>
40void 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
Generic library namespace.
Definition atlasconv.h:45
void Shuffle(std::vector< C > &v)
Randomly reorder the contents of a std::vector.
Definition shuffle.h:40