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/randgen.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 unsigned pos = v.size(); 00044 00045 if(!pos) // handle size() == 0 nicely 00046 return; 00047 00048 // This swaps each element with one of the ones before 00049 // it, starting with the last element. Essentially, 00050 // this generates an operation from the permutation 00051 // group of size() elements, and applies it to the 00052 // vector. Note that the loop only executes size() - 1 00053 // times, as element 0 has nothing to swap with. 00054 while(--pos) { 00055 unsigned new_pos = IRand(pos + 1); // 0 <= new_pos <= pos 00056 if(new_pos == pos) 00057 continue; 00058 C tmp = v[pos]; 00059 v[pos] = v[new_pos]; 00060 v[new_pos] = tmp; 00061 } 00062 } 00063 00064 } // namespace WFMath 00065 00066 #endif // WFMATH_SHUFFLE_H