Случайный выбор элемента при неизвестном их количестве

Как можно выбрать один из n объектов случайным образом, если объекты предъявляются последовательно, но их количество n заранее неизвестно?

Задача достаточно актуальна в программировании при работе с файловой системой: как наиболее быстро выбрать случайный файл в директории?

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

Для таких случаев существует быстрый и красивый алгоритм:

Первую строку мы выбираем всегда, вторую — с вероятностью 1/2, третью — с вероятностью 1/3 и так далее. К концу процесса вероятность выбора всех строк окажется одинаковой(1/n, где n - неизвестное общее количество элементов)!

i = 0
while (<пока есть непройденные элементы>)
  /* randint - случайное число "от" и "до" */
  if randint(1, ++i) == 1
    choice = i
 
/* после выполнения имеем в choice - 
   искомый случайный выбор */

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

 Чтение случайного файла в директории не зная общее количество файлов в этой директории ссылка |режим:

$i = 0;
$randomFileName = '';
if ($handle = opendir('d:/ourdir/')) {
   while (false !== ($file = readdir($handle))) {
       // Пропускаем ссылки на текущую и родительскую
       // директории
       if ($file == "." || $file == "..") continue;
 
       // Случайно выбираем файл
       if (mt_rand(1, ++$i) == 1) {
           $randomFileName = $file
       }
   }
   closedir($handle);
}
 
print "Имя выбранного случайного файла: $randomFileName";

$i = 0; $randomFileName = ''; if ($handle = opendir('d:/ourdir/')) { while (false !== ($file = readdir($handle))) { // Пропускаем ссылки на текущую и родительскую // директории if ($file == "." || $file == "..") continue; // Случайно выбираем файл if (mt_rand(1, ++$i) == 1) { $randomFileName = $file } } closedir($handle); } print "Имя выбранного случайного файла: $randomFileName";

В результате получаем имя случайно выбранного файла

Тестировалось на: Apache 1.3.33, PHP 5.0