Генерация произвольных чисел и перестановок в C++

C++   7 Январь 2012  Автор статьи:  

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

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

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

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

Реализация

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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, которая действует по этому же алгоритму, но для лучшего понимания приведем реализацию.

Реализация

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdlib>
#include <ctime>
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;
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++