Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Генерация куска случайной перестановки

Автор: SickFxck 15.4.2011, 20:33

Кто-нибудь знает эффективный алгоритм генерации не всей перестановки, а заранее указанного "отрезка" массива, содержащего перестановку?

Пример. Есть числа от 1 до 10 и есть какая-то её перестановка (массив чисел):

Код

5 8 1 9 6 4 2 7 3 10

, которая определяется просто каким-то числом (seed для генератора псевдослучайных чисел) в программе. Реально такой массив не собираюсь генерировать, поскольку N может быть очень большим.
Также дан диапазон индексов, который требуется получить из этого массива. К примеру, 5-9, т.е. нужно получить следующие элементы: "4 2 7 3 10", не генерируя все предыдущие, т.к. они мне не нужны.

Очевидно, что обычный алгоритм вроде (псевдокод)

Код


set_random_generator_seed(123);

for(i = 0; i < N; i++)
{
    arr.swap(i, random(i, N - 1));
}

требует генерации всех чисел (от первого элемента до верхней границы диапазона).

Добавлено через 4 минуты и 19 секунд
Я правда с описанием немного намудрил. Если гораздо короче: как получить i-й элемент какой-то определённой перестановки чисел от 1 до N, не генерируя все (или большую часть) остальных элементов перестановки? Сама перестановка определяется каким-то числом.

Автор: миг 16.4.2011, 07:59

Я бы сделал так. чтобы найти случайное число на отрезке от i до k. Нужно с генерировать любое случайное число(думаю ваш компилятор умеет это делать). Найти остаток от деления на число k. Затем проверить условие, чтобы число i было меньше или равно остатку от деления.

Автор: SickFxck 16.4.2011, 14:12

миг, вы о чём вообще?

Автор: _Y_ 16.4.2011, 14:29

Цитата(SickFxck @ 15.4.2011, 20:33

)

Если гораздо короче: как получить i-й элемент какой-то определённой перестановки чисел от 1 до N, не генерируя все (или большую часть) остальных элементов перестановки?

Если я правильно понял это требование, то решения не существует. Во всяком случае, для случайных перестановок. Сам принцип метода Монте Карло заключается в том, что результат можно воспроизвести только воспроизведя все "броски костей" (да и то только если генератор случайных чисел выдает числа псевдослучайные).

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

Автор: SickFxck 16.4.2011, 20:03

Спасибо.