Генерация произвольных чисел и перестановок в C++
Пусть требуется сгенерировать произвольное целое число типа 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;
}