Fisher-Yates shuffle

fisheryates.cpp

#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std ;

int randInt( int a, int b )
{
  return a + rand()%(b-a) ;
}

inline vector<int> randomOrder( int maxVal )
{
  vector<int> results ;
  
  // fisher-yates
  vector<int> indices( maxVal ) ;
  
  // "fill the hat with numbers", in order
  for( int i = 0 ; i < maxVal ; i++ )
    indices[i] = i ;
  
  // indices:  0 1 2 3 4
  
  // Now push random indices into songIndexShuffledOrder
  // do this n times.
  for( int i = 0 ; i < maxVal ; i++ )
  {
    // starts: 5
    int numsRem = maxVal - i ;
    
    // random number on [0,4]
    int index = randInt( 0, numsRem ) ;
    
    // say you got 3, then you will add 3 into the order array:
    // indices:    0 1 2 3 4
    // songOrder:  3
    results.push_back( indices[index] ) ;

    // This next step is what prevents repeat.
    // Now swap indices, the BACK elt with the JUST SELECTED elt.
    // indices:    0 1 2 4 //3
    // Now on the next iteration, __3 will no longer be selected__,
    // because i=1, so the max # will be 3.
    ::swap( indices[index], indices[numsRem-1] ) ;
  }
  
  return results ;
}

int main()
{
  vector<int> t = randomOrder( 6 ) ;
  for( int a : t )
    printf( "%d\n", a ) ;
}