00001 // randgen.h (random number functions) 00002 // 00003 // The WorldForge Project 00004 // Copyright (C) 2002 The WorldForge Project 00005 // 00006 // This program is free software; you can redistribute it and/or modify 00007 // it under the terms of the GNU General Public License as published by 00008 // the Free Software Foundation; either version 2 of the License, or 00009 // (at your option) any later version. 00010 // 00011 // This program is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 // 00016 // You should have received a copy of the GNU General Public License 00017 // along with this program; if not, write to the Free Software 00018 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00019 // 00020 // For information about WorldForge and its authors, please contact 00021 // the Worldforge Web Site at http://www.worldforge.org. 00022 00023 // Author: Ron Steinke 00024 // Created: 2002-5-23 00025 00026 #ifndef WFMATH_SHUFFLE_H 00027 #define WFMATH_SHUFFLE_H 00028 00029 #include <vector> 00030 00031 #include <wfmath/const.h> 00032 #include <wfmath/MersenneTwister.h> 00033 00034 namespace WFMath { 00035 00037 00040 template<class C> 00041 void Shuffle(std::vector<C>& v) // need vector for random access 00042 { 00043 typedef typename std::vector<C>::size_type size_type; 00044 size_type pos = v.size(); 00045 00046 if(!pos) // handle size() == 0 nicely 00047 return; 00048 00049 // This swaps each element with one of the ones before 00050 // it, starting with the last element. Essentially, 00051 // this generates an operation from the permutation 00052 // group of size() elements, and applies it to the 00053 // vector. Note that the loop only executes size() - 1 00054 // times, as element 0 has nothing to swap with. 00055 while(--pos) { 00056 size_type new_pos = MTRand::instance.randInt(pos); // 0 <= new_pos <= pos 00057 if(new_pos == pos) 00058 continue; 00059 C tmp = v[pos]; 00060 v[pos] = v[new_pos]; 00061 v[new_pos] = tmp; 00062 } 00063 } 00064 00065 } // namespace WFMath 00066 00067 #endif // WFMATH_SHUFFLE_H