VRPH  1.0
src/RNG.cpp
Go to the documentation of this file.
00001 
00002 //                                                        //
00003 // This file is part of the VRPH software package for     //
00004 // generating solutions to vehicle routing problems.      //
00005 // VRPH was developed by Chris Groer (cgroer@gmail.com).  //
00006 //                                                        //
00007 // (c) Copyright 2010 Chris Groer.                        //
00008 // All Rights Reserved.  VRPH is licensed under the       //
00009 // Common Public License.  See LICENSE file for details.  //
00010 //                                                        //
00012 
00013 #include "VRPH.h"
00014 #define MODULUS 2147483647
00015 #define MULT 16807
00016 
00017 // A collection of random seeds from Mathematica for the LCG - 
00018 
00019 static long long zrng[]=
00020 {
00021 1585898122, 977263903, 1405617513, 992686252, 18121536, 2063068841, 
00022 754752318, 41984681, 105083035, 139298838, 185623219, 949931193, 
00023 844017127, 220735746, 2086518219, 1159920248, 223790403, 521639770, 
00024 383329278, 1351669096, 546508335, 241074248, 1250430659, 1360027002, 
00025 2133008156, 801417619, 234137012, 820590974, 208037679, 762045751, 
00026 1878813713, 238884113, 1183679960, 1043965154, 976700693, 2008340726, 
00027 677399582, 1285359843, 1138040391, 468728879, 1173244317, 235237876, 
00028 1232346133, 471001204, 1863659670, 1165359604, 1863730245, 
00029 1039575367, 33196368, 447728821, 803148007, 732593271, 1682165068, 
00030 1423782112, 2088550953, 936772830, 1669565296, 1410105093, 
00031 1883854503, 157181746, 237269108, 530564635, 448848243, 286675281, 
00032 363322466, 861763630, 825225764, 1406888526, 1616456635, 916354297, 
00033 1567694919, 1200774035, 81218620, 54228387, 964954038, 392387524, 
00034 1451979814, 2122793904, 1202721819, 628095876, 1098922114, 95833991, 
00035 1140244378, 2013076662, 1482101325, 815732936, 154659849, 1575364612, 
00036 1969394111, 2057580375, 2015360901, 1435017398, 1311586731, 
00037 314500068, 162190131, 1309049839, 1760010706, 827285638, 554810512, 
00038 942750612, 1888673353, 1658410347, 1535796884, 610141401, 1095089179, 
00039 473990272, 1591707931, 1650890892, 2129059111, 409806116, 739034658, 
00040 1074994661, 1150159741, 269214387, 1516429880, 1369667127, 
00041 2122951567, 1536355824, 1947835842, 823114858, 2001677049, 243498667, 
00042 438835589, 2084577438, 1778854242, 1589215500, 993105500, 1399779082, 
00043 680250157, 987051556, 1597580442, 71887978, 974657481, 665567351, 
00044 689482979, 1947413384, 1450689852, 1817370782, 1249183224, 94259407, 
00045 1576903163, 194915665, 1059712692, 453727562, 2124585319, 1602930620, 
00046 1142904759, 965673653, 246108792, 1654947015, 1878828492, 567267685, 
00047 878355741, 881707113, 580077084, 901920333, 518339521, 1010914174, 
00048 1742574627, 1097862854, 1000362984, 1022589700, 821089113, 
00049 2040587093, 350389248, 322891321, 1159453516, 614435100, 485423061, 
00050 580074455, 1038514233, 582690813, 1394060287, 1193771124, 2030353361, 
00051 1331961065, 1091003721, 480683205, 172421798, 1314856444, 1020643186, 
00052 161954324, 1198718865, 1108252489, 696760670, 1050697945, 871635855, 
00053 485876747, 179770165, 2110038934, 1877118219, 1944112804, 889651228, 
00054 1709232582, 1021461548, 1062416269, 1775284287, 1548647752, 
00055 1468622131, 1501559878, 1641100862, 2043157460, 9225604, 516609908, 
00056 1918652536, 890178664, 2139455918, 723888229, 380523573, 998128782, 
00057 2122099165, 193945359, 1163177060, 496833754, 1752971070, 842393719, 
00058 651771348, 357600681, 448174576, 1539044660, 1204659744, 526302849, 
00059 1683442778, 2055374782, 2096711886, 1847065567, 2103775300, 
00060 1867545195, 180757560, 756099417, 2122354186, 911394104, 377306975, 
00061 1060803589, 1558009924, 1147998809, 30263572, 545721691, 1043063797, 
00062 982875671, 170326373, 1003183201, 6932742, 567081165, 1339773006, 
00063 668884182, 469588686, 1338125418, 1959613029, 1576328955, 1873529200, 
00064 501967489, 85306291, 1735183136, 2001471533, 960275626, 130336187, 
00065 1334655399, 1331594739, 345982965, 590996008, 1535438073, 1316368256, 
00066 401559792, 122512210, 1415929389, 1011799313, 1869058634, 1064463722, 
00067 1447264924, 474372764, 134983996, 1166979876, 2140794736, 1078919141, 
00068 564009419, 1273245050, 212505753, 650918775, 1716276860, 1008717539, 
00069 1491859263, 2098344229, 1700342627, 2098195790, 702806311, 430088402, 
00070 1841775273, 873208521, 2015656192, 1659123069, 935557457, 1250857761, 
00071 206689908, 1035486424, 410559828, 883746510, 1317520915, 1194730483, 
00072 121224379};
00073 
00074 #if VRPH_ADD_ENTROPY
00075     static int initialized=0;
00076 #endif
00077 
00078 
00079 double lcgrand(int stream)
00080 {    
00084 
00085     long long zi;
00086 #if VRPH_ADD_ENTROPY
00087     // Add a time component to the RNG to get different
00088     // results on different runs.
00089 
00090     if(!initialized)
00091     {
00092         time_t now;
00093         time(&now);
00094         srand((unsigned int)now);
00095         zrng[stream]+=rand();
00096 
00097         initialized=1;
00098 
00099     }
00100 #endif
00101 
00102     zi= zrng[stream];    
00103     
00104     zrng[stream]=(MULT*zi) % MODULUS;
00105     //Update the state of the RNG    
00106 
00107     return((double)zrng[stream]/MODULUS);
00108 }
00109 
00110 void random_permutation(int *perm, int n)
00111 {
00117 
00118     int r, len, temp;
00119 
00120     len = n-1;
00121 
00122     while(len >= 0)
00123     {
00124         r= (int)( lcgrand(9) * n);//between 0 and n-1 inclusive
00125         if(r<0)
00126             r=0;
00127         if(r>n-1)
00128             r=n-1;
00129         temp=perm[len];
00130         perm[len]=perm[r];
00131         perm[r]=temp;
00132         len--;
00133     }
00134 
00135     
00136     return;
00137 }
00138 
00139