случайная перестановка

Не то, что вы точно просили, но если предоставлено генератор случайных чисел вас не устраивает, может, стоит попробовать что-нибудь другое. Как правило, генерация псевдослучайных чисел может быть очень простой.

Вероятно, самый известный алгоритм
http://en.wikipedia.org/wiki/Linear_congruential_generator

Подробнее
http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators

Сгенерируйте N чисел (N <необходимого вам случайного числа) перед выполнением вычислений или сохраните их в массиве как данные с помощью вашего медленного, но хорошего генератора случайных чисел; затем выберите число, просто увеличивая индекс в массиве внутри вашего вычислительного цикла; если вам нужны разные семена, создайте несколько таблиц.

Создает 32 целое число. Для каждого индекса i (возможно, только до половины числа элементов в массиве), если бит i% 32 равен 1 , поменять местами i с n - i - 1 .

Конечно, это может быть недостаточно случайным для ваших целей. Вы, вероятно, могли бы улучшить это, не заменяя n - i - 1 , а используя другую функцию, примененную к n и i , которая дает лучшее распределение. Вы даже можете использовать две функции: одну, когда бит равен 0 , и другую, когда он равен 1 .

Как показывают другие ответы, вы можете сделать случайное целое число в диапазоне от 0 до N! и используйте его для воспроизведения в случайном порядке. Хотя теоретически это правильно, в целом это не будет быстрее, поскольку N! быстро растет, и вы будете проводить все свое время, занимаясь арифметикой bigint.

Если вам нужна скорость и вы не возражаете против некоторой случайности, вам будет гораздо лучше использовать менее хороший генератор случайных чисел. Линейный конгруэнтный генератор (см. http://en.wikipedia.org/wiki/Linear_congruential_generator ) выдаст вам случайное число за несколько циклов.

Генерация случайного числа занимает много времени, вы говорите? Реализация Javas Random.nextInt примерно

oldseed = seed;
nextseed = (oldseed * multiplier + addend) & mask;
return (int)(nextseed >>> (48 - bits));

Это слишком много работы для каждого элемента?

Обычно нет необходимости в полном диапазоне следующего случайного значения, поэтому, чтобы использовать точно такое же количество случайности, вы можете использовать следующий подход (который почти как random (0, N!) , Наверное):

// ...
m = 1; // range of random buffer (single variant)
r = 0; // random buffer (number zero)
// ... 
for(/* ... */) {
    while (m < n) { // range of our buffer is too narrow for "n"
        r = r*RAND_MAX + random(); // add another random to our random-buffer
        m *= RAND_MAX; // update range of random-buffer
    }
    x = r % n; // pull-out  next random with range "n"
    r /= n; // remove it from random-buffer
    m /= n; // fix range of random-buffer
    // ...
}

PS Конечно, будут ошибки, связанные с делением на значения, отличные от 2 ^ n, но они будут распределены между приведенными выборками.