Отступление Экспериментальное исследование эффективности алгоритмов

какому ансамблю?
Повторяющиеся элементы? - зависит от задания…
Тип, диапазон (например, 1..n)?
“n!” ? (см.далее)
Что измерять?
Число операций, время.
Как измерять? (при малых и больших значениях n), (см.код Бентли, в папке «программа»/ tm1.cpp)
Контроль правильности результата… (отличие выборочных тестов от массовой генерации)

индукционную схему:
на i-ом шаге первые i элементов составляют равновероятную (среди всех i!) случайную перестановку:
База. Один элемент является единственной случайной перестановкой из одного элемента.
Предположение. Предположим, что на (i − 1)-ом шаге первые (i − 1) элементов составляют равновероятную случайную перестановку.
Переход. Перейдем от (i − 1)-го шага к i-му: возьмем случайный индекс от 1 до i, поставим i-ый элемент на место этого индекса, а тот элемент, который стоял по этому индексу до операции, поставим на место номер i.
Очевидно, что таким образом можно получить всевозможные перестановки первых i элементов и при этом они будут равновероятны.

randseed Зерно случайного генератора
*/
void shuffle( intrandseed ) {
sedge t;
int rind;
int i;
/* инициализация генератора случайных чисел: */
srand( randseed );
for(i=0; i rind = (i==0) ? 0 : rand()%i;
t = e[i]; e[i] = e[rind]; e[rind] = t;
}
}