На этом шаге мы рассмотрим алгоритмы, переставляющие элементы в случайном порядке.

    Для выполнения случайной перестановки элементов существуют следующие алгоритмы:

  void
  random_shuffle (RandomAccessIterator beg, RandomAccessIterator end)
  void
  random_shuffle (RandomAccessIterator beg, RandomAccessIterator end, RandomFunc& op)

    Первая форма переставляет элементы интервала [beg,end) в случайном порядке, для чего используется генератор случайных чисел с равномерным распределением.

    Вторая форма переставляет элементы интервала [beg,end) с использованием операции ор, вызываемой для целого значения типа difference_type итератора: op(max). Операция ор возвращает случайное число, большее либо равное 0, но меньшее max (возвращать max нельзя).

    Учтите, что операция ор является неконстантной ссылкой, что исключает использование временных значений или обычных функций.

    Сложность линейная (numberOfElements-1 обменов).

    Возможно, вас интересует, почему алгоритм random_shuffle() использует необязательную операцию как неконстантную ссылку. Дело в том, что генераторы случайных чисел обычно обладают локальным состоянием. Старые глобальные функции С (такие, как rand()) хранят свое локальное состояние в статических переменных. Однако такой подход имеет свои недостатки: в частности, генератор случайных чисел в принципе небезопасен по отношению к потокам выполнения (threads), поэтому вы не сможете сгенерировать два независимых потока данных (streams), состоящих из случайных чисел. По этой причине лучше воспользоваться объектами функций, локальное состояние которых инкапсулируется в переменных класса. Но это означает, что генераторы случайных чисел не могут быть константными, потому что они должны изменять свое локальное состояние при создании нового случайного числа. Чтобы генератор случайных чисел не был константным, его можно передать по значению вместо передачи по неконстантной ссылке. Но в этом случае генератор будет копироваться вместе со своим состоянием, и при каждой передаче генератора алгоритму будет генерироваться одна и та же псевдослучайная последовательность. С учетом всех перечисленных факторов было решено передавать генератор по неконстантной ссьшке.

    Если вам потребуется использовать одну последовательность случайных чисел дважды, ее можно просто скопировать. Но если генератор основан на применении глобального состояния, вы будете получать разные последовательности. Следующий пример демонстрирует случайную перестановку элементов с использованием алгоритма random_shuffle():

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

class MyRandom {
  public:
    ptrdiff_t operator() (ptrdiff_t max) {
        double tmp;
        tmp = static_cast<double>(rand())
                / static_cast<double>(RAND_MAX);
        return static_cast<ptrdiff_t>(tmp * max);
    }
};


int main()
{
  vector<int> coll;

  INSERT_ELEMENTS(coll,1,9);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Случайная перестановка элементов
  random_shuffle (coll.begin(), coll.end());

  PRINT_ELEMENTS(coll,"Случайная перестановка элементов:\n");

  // Повторная сортировка
  sort (coll.begin(), coll.end());
  PRINT_ELEMENTS(coll,"Сортировка:\n");

  // Случайная перестановка элементов
  //   с пользовательским генератором случайных чисел
  //   - для передачи l-значения необходимо использовать временный объект
  MyRandom rd;
  random_shuffle (coll.begin(), coll.end(),    // Интервал
                  rd);                 // Генератор случайных чисел

  PRINT_ELEMENTS(coll,"Конечная коллекция:\n");


  getch();
  return 0;
}

//---------------------------------------------------------------------------

    При втором вызове алгоритма random_shuftle() используется пользовательский генератор случайных чисел rd(). Он представляет собой объект вспомогательного класса MyRandom, который задействует алгоритм построения случайных чисел, часто обеспечивающий лучший результат по сравнению с прямым вызовом rand().

    Возможный (но не гарантированный) результат выполнения программы выглядит так:

Рис.1. Результат выполнения приложения

    На следующем шаге мы рассмотрим перемещение элементов в начало.

Предыдущий шаг Содержание Следующий шаг