Пусть требуется сгенерировать произвольное целое число типа int. Для этого можно воспользоваться встроенной функций rand, однако в этом случае могут возникнуть проблемы в связи с тем, что функция rand генерирует в худшем случае лишь 16-битные числа (в зависимости от реализации). Поэтому для генерации произвольного числа лучше воспользоваться следующим методом.

Описание метода

Как известно, в C++ число типа int содержит 4 байта, то есть 32 бита. Следовательно, можно условно разбить число на два 16-битных и каждую из этих частей генерировать с помощью встроенной функции rand. Чтобы «склеить» эти две части в одно число используются операции побитового сдвига и «исключающего или» (XOR).

В качестве примера использования этого метода приведем реализацию функции, которая возвращает произвольное число из промежутка [first, last), а также вспомогательной функции, возвращающей произвольное число из промежутка [0, m).

Реализация


int random (int m)
{
// Опишем переменную, в которой будем хранить возвращаемое значение
int result;

// Произвольно "заполним" 16 старших бит
result = rand() << 16; // И сделаем то же самое с 16 младшими битами // С помощью операции XOR "объединим" эти две части result ^= rand(); // Возвращаем произвольное число из промежутка [0, m) return abs (result) % m; } int random (int first, int last) { // Возвращаем произвольное число из промежутка [first, last) return first + random (last - first); }
Замечание: Взятие по модулю переменной result в реализации функции int random (int m) необходимо, так как int - знаковый тип. После заполнения 16 старших бит знаковый бит мог стать равен 1 и переменная result стала бы отрицательной.

Генерация произвольной перестановки

Для генерации произвольной перестановки воспользуемся вышеописанным методом генерации произвольного числа. Пусть имеет тождественная перестановка, то есть перестановка, в которой на первой позиции стоит 1, на второй - 2 и т.д. Будем последовательно двигаться по элементам перестановки. На i-ом шаге элемент, на котором сейчас стоит указатель, поменяем местами с произвольно выбранным элементом, номер которого лежит в промежутке [i, n), т.е. i-ый элемент может и остаться на своем месте.

Очевидно, после этих преобразований элементы перестановки произвольное перемешаются. В C++ есть встроенная функция random_shuffle, которая действует по этому же алгоритму, но для лучшего понимания приведем реализацию.

Реализация


#include
#include
#include
using namespace std;

int random (int m)
{
return abs ((rand() << 16) ^ rand()) % m; } int random (int first, int last) { return first + random (last - first); } int main () { srand (time (NULL)); // Поместим в массив тождественную перестановку int a[] = {1, 2, 3, 4, 5, 6}; // Введем переменную, отвечающую за число элементов массива int n = 6; // После завершения цикла получим произвольную перестановку for (int i = 0; i < n - 1; i++) swap (a[i], a[random (i, n)]); return 0; }